Questions tagged [graph-theory]

Questions about the branch of combinatorics called graph theory (not to be used for questions concerning the graph of a function). This tag can be further specialized via using it in combination with more specialized tags such as extremal-graph-theory, spectral-graph-theory, algebraic-graph-theory, topological-graph-theory, random-graphs, graph-colorings and several others.

3,400 questions
180 views

$R(3,6) = 18$, especially proving that $R(3,6)>17$

I'm studying the Ramsey numbers, especially $R(3,6) = 18$ I understand that the proof using the theorem $R(m,n) <R(m-1,n)+R(m,n-1)$ can only prove that $R(3,6)<20$. However by Cariolaro's "On ...
806 views

Does the hypergraph of subgroups determine a group?

A hypergraph is a pair $H=(V,E)$ where $V\neq \emptyset$ is a set and $E\subseteq{\cal P}(V)$ is a collection of subsets of $V$. We say two hypergraphs $H_i=(V_i, E_i)$ for $i=1,2$ are isomorphic if ...
211 views

Blocking $a\to b\to c$ in a DAG with bounded degrees

(This is an (easy-looking) toy question for this one.) Question. Find the smallest $\alpha$ satisfying the following: Let $G=(V,E)$ be a finite directed acyclic graph, where each in- and out-...
498 views

A Modern Proof of Erdos and Renyi's 1959 Random Graph Paper?

In their paper, Erdos and Renyi consider a random graph with a fixed number of edges, as opposed to the more modern approach of adding each edge independently with probability $p$. From what I ...
68 views

256 views

Number of (distinct) knots with a bounded number of crossings

The title pretty much covers it: are there good (asymptotic) estimates on the number of knot types whose projection has at most $N$ crossings? Similar question with "projection" replaced by "...
85 views

Minimize edge number under diameter and max-degree constraint

Given a number n of nodes, a diameter d (d>1) and a max-degree k. Let's assume d and k are chosen such that a graph with n nodes with the desired diameter and max-degree exists. What is the minimum ...
96 views

Find all paths on undirected Graph [closed]

I have an undirected graph and i want to list all possible paths from a starting node. Each connection between 2 nodes is unique in a listed path is unique, for example give this graph representation:...
55 views

Vertex cover number vs matching number

Let $G=(V,E)$ be a finite, simple, undirected graph. A matching is a set $M\subseteq E$ of pairwise disjoint edges. A vertex cover is a set $C\subseteq V$ of vertices such that $C\cap e \neq \emptyset$...
101 views

$\mathrm{NP}$-complete problems in graph theory: undirected vs. directed

Is it true that it is much easier to establish $\mathrm{NP}$-complete on undirected graphs than digraphs (directed graph)? Academic articles proving $\mathrm{NP}$-completeness of problems on ...
133 views

Groups inducing edge-colorings on graphs. Is this concept known?

Are the following concepts known in graph/group theory, and if Yes, what are they called and where to read about them? Because I do not know better, I gave them placeholder names for now. 1. ...
100 views

Constructing an n-node DAG, with exactly k paths between node 1 and node n [closed]

Pretty straight forward, yet I didn't find how to approach such a problem. I tried constructing a solution from the reverse problem (Given a DAG count the number of paths between node 1 and node n), ...
67 views

Tutte polynomial from independent sets of a graph

Let $G$ be a connected graph with chromatic polynomial $X(G,q)$. Since $k$-proper coloring a graph is same as partitioning the vertex set $V$ into $k$ independent sets (a subset of the vertex set in ...
201 views

How to find a random cycle in a large graph?

Suppose we have a large directed graph $G$ with no self-cycle and no more than one edge between two nodes, for example, containing about 2000 nodes and about 10 edges per node. Now we need to achieve ...
133 views

IH-moves on trivalent graphs, and a complex that might be known to low-dimensional topologists

Here is a combinatorial problem which is hard to Google but seems like it might have a solution well known to people who study finite type invariants etc. Let $G_{g,b}$ denote the set of finite ...
161 views

193 views

Can two non-equivalent polytopes of same dimension have the same graph?

By a polytope I mean the convex hull of finitely many points. The graph of a polytope is the graph isomorphic to its 1-skeleton. By equivalence of polytopes I mean combinatorial equivalence, i.e. ...
178 views

Maximum number of triangles no two of which have a common edge

For $n\in N_+$, define f(n) to be that for any n-vertice graph G, if any two triangle in G don't have a common edge, then G has at most f(n) triangles. Do we have some good estimates for f(n)? By ...
68 views

Transfer-impedance matrix for edge correlations in random spanning tree

Suppose $G$ is a (weighted) connected graph and let $T$ denote a random spanning tree of $G$, chosen uniformly (or respecting the edge weights). It is known that for any distinct edges $e, f$ \...
47 views

Interesting First-Order Properties of Hypercubes and Grids

Hypercubes: The $n$-hypercube is the graph $H_n$ whose vertex set $V(H_n)$ consists of all binary string of length $n$, and the edges are pairs of the form $\{w,w'\}$ where $w$ and $w'$ differ in ...
109 views

Increasing the chromatic number by “folding” two vertices of distance 2

Is there a finite, connected, simple, undirected graph $G=(V,E)$ such that $G$ is not complete, and whenever two vertices of distance $2$ are identified ("folded"), then the chromatic number ...
64 views

Reconstructing plane graphs from degree- and face-sequences

Let $G$ be a plane $3$-connected graph; so it partitions the plane into regions bounded by faces. Let $\mathrm{deg}_v$ be the sequence of vertex degrees of $G$, and $\mathrm{deg}_f$ be the sequence of ...
340 views

How many vertices can a self-complementary graph have?

Counting edges easily shows that if $n$ is congruent to 2 or 3 modulo 4, there is no self-complementary graph on $n$ vertices. Is the converse true? What I know: Paley graphs are self-complementary,...
80 views

Is there an infinite, simple, undirected graph $G=(V,E)$ such that there is $n\in\mathbb{N}$ with the following properties? $K_n$ is a minor of $G$, but $K_{n+1}$ is not a minor of $G$, and if $F$ ...
33 views

Graph homomorphism from a high-girth graph to the sub-graph of a high-girth graph

Consider a classical result: There are degree-$d$ (appropriate random) graphs on $n$ vertices with girth $\Omega(\log n/\log d)$ of chromatic number $\Omega(d/\log d)$ for arbitrary large $n$. We can ...
I am trying to resolve the following problem and was wondering if there already exists consecrated algorithms to solve it. Let $G(V,E)$ be a weighted graph with vertices $V$ connected through ...
Let $G=(V,E)$ be a directed acyclic graph. Define the set of all directed paths in $G$ by $\Gamma$. Given a subset $W\subseteq V$, let $\Gamma_W\subseteq \Gamma$ be the set of all paths in $\Gamma$ ...