# 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.

4,860 questions
Filter by
Sorted by
Tagged with
12 views

### Relation between the left-dominant eigenvectors (eigenvector corresponding to 0 eigenvalue) of two Laplacian matrices

Let $G_1=(v,\epsilon_1)$,$G_2=(v,\epsilon_2)$ be two graphs with the same set of vertices and $\epsilon_1 \subset \epsilon_2$. $L_1$ and $L_2$ be the Laplacian matrices associated with graph $G_1$ and ...
139 views

### Catalan numbers from matchings?

There are several examples of interpreting the Catalan numbers as non-nesting or non-crossing matchings of some graph. My question is: Is there a family of graphs $G_1,G_2,\dotsc$ with the number of ...
• 15.2k
20 views

### Applicability of matching to tour improvement

Question: what are relevant publications that deal with matching as a means of constructing shorter tours from existing ones? The reason for asking is that I couldn't find anything in that respect ...
• 11.7k
23 views

### The number of maximal cliques of the intersection graphs

Are there some results about the upper bound of the number of maximal cliques (NMC) of some class of intersection graphs? I want to know whether some classic classes of intersection graphs have ...
• 1,473
42 views

### "How often" does pseudo-isomorphicity imply isomorphicity in graphs?

Motivation. The iterated degree matrix $\mathbb{D}(G)$ of a finite simple undirected graph $G$ gives $G$ a kind of "fingerprint" for $G$ that is calculable in polynomial time. When for two ...
65 views

### Does it help for graph isomorphism to know power of the permutation matrix?

Here all matrices are square $n \times n$ with integer entries. If you prefer, all entries are $0-1$. Observation: the discrete logarithm for permutation matrices is polynomial in $n$, since the ...
• 23.7k
1 vote
53 views

### Min-sum belief propagation not working on a chain model with equal unary potentials

Given is a chain factor graph as presented in the image below with the following properties: Each node can take values 0 or 1 All unary potentials are equal (e.g. $U(a)=0$) for every node $a$ All ...
83 views

### Dense vertex-symmetric graphs with high girth

I am looking for existing constructions of vertex-symmetric graphs on $n$ nodes that have a girth at least $g$ and are dense, i.e., have at least $n^{1 + \epsilon}$ edges, where $\epsilon>0$ may ...
130 views

### Extension of Erdős-Gallai (s,t)-path theorem to directed graphs

The following is a result of Erdős-Gallai from 1959 (https://link.springer.com/article/10.1007/BF02024498): Given a 2-connected undirected unweighted graph with minimum degree at least $d$, for every ...
52 views

### Decompose directed graph into many cycles

Given is a directed graph $G$, possibly with self-loops or parallel edges, such that each vertex has the same in-degree as out-degree. I would like to decompose it into as many directed cycles as ...
• 143
134 views

248 views

### Does every infinite, connected, locally finite, vertex-transitive graph have a leafless spanning tree?

My question is Let $G$ be an infinite, connected, locally finite, vertex-transitive graph. Must $G$ have the following substructures? i) a leafless spanning tree; ii) a spanning forest consisting ...
• 1,644
42 views

### Maximum number of h-dimensional hyper-edges without forming any (h+1) complete subgraph

This is about graph theory. Define an h-dimensional hyperedge as a set that contains h vertices. A graph of (h+1) vertices is h-complete if any h combination (or any subset with size h) is an h-...
• 23
215 views

• 234
89 views

### Can we calculate the spectral radius of the universal cover for specific graphs?

Background For a finite graph $G$, let $\tilde{G}$ denote the universal cover of $G$. For a vertex $v$, let $p_{2n}(v)$ denote the number of paths of length $2n$ that start and end at $v$. The ...
• 11k
132 views

### For every partition of $E(K_{n,n})$ into $n$ colour classes of size $n$, there is a vertex incident to at least $\sqrt{n}$ colours

Given a partition of the edges of $K_{n,n}$ into $n$ colours, where each colour appears exactly $n$ times, prove that there exists a vertex incident to at least $\sqrt{n}$ colours.
94 views

### Maximal graphs with a property that is invariant w.r.t. vertex removal

Let $P$ be a property of graphs such that if a graph $G$ has $P$, then any graph obtained from $G$ by removal of a vertex also has $P$. Let $g(n)$ be the maximum size of a graph of order $n$ having $P$...
143 views

### 3D analog of the Petersen graph

If you arrange the edge skeletons of a convex regular pentagon and a regular pentagram in the right way and connect each vertex of the former to that of the latter lying under it, the result (the ...
• 2,414
1 vote
43 views

### A multi-layer version of Menger's theorem

Menger's theorem says that the maximum number of pairwise disjoint paths between two vertex sets $L,R$ of a graph G equals the minimum size of an $L$-$R$ separator. Below is a generalisation with more ...
• 1,644
97 views

### Cover a graph with small size complete graphs

Given a complete graph with $n$ nodes, if we want to use $n$ complete subgraphs to cover the graph and ask what is the minimum possible size of each complete subgraph, the answer is $\Theta(\sqrt{n})$:...
• 43
125 views

### Can a polytopal graph be "centrally symmetric" in more than one way?

Let $P,Q$ be two centrally symmetric convex polytopes, potentially of different dimensions and combinatorial type, but with the same edge-graph $G$. The central symmetry of $P$ induces an involutory ...
• 11.3k
1 vote
44 views

### What is the complexity of deciding if the number of independent sets in a graph exceeds a given threshold?

Given an (undirected) graph G, let i(G) be the number of independent sets  in G. Given also a threshold th, the problem is to decide whether $i(G) > th$. Are there known values of th for which ...
• 11
105 views

### Independent sets in graphs with girth $\ge g$

A well known off-diagonal Ramsey result says that every $C_3$-free graph $G$ on $N$ vertices has an independent set of size $\Omega(\sqrt{N\log N})$. It is a conjecture of Erdos that every $C_4$-free ...
• 2,198
138 views

I have come across the following problem. Let $d\in\mathbb{N}$. Let $G$ be any $k$-regular connected directed graph with $n$ vertices, no parallel edges and no 2-cycles. For a vertex $v\in G$, let $... • 167 8 votes 0 answers 227 views ### Goldberg-Seymour conjecture I am wondering whether the graph theory community regards the Goldberg-Seymour conjecture as settled. According to the Wikipedia entry on the Goldberg-Seymour conjecture, "In 2019, an alleged ... • 18.8k 1 vote 0 answers 107 views ### Independence number of a grid like graph Given natural numbers$n$and$k$, let$G_{n,k}$denote the simple graph whose vertex set is$\{1,2,\ldots ,n\}$and there is an edge between$i$and$j$when$|i-j|\leq k$. I am interested in the ... • 1,205 2 votes 1 answer 81 views ### Strongly regular graphs with certain parameters Does there exist a sequence of strongly regular graphs with parameters$(n,d,\lambda,\mu)$(so every pair of adjacent vertices have$\lambda$common neighbours, and every pair of non-adjacent ones ... 1 vote 0 answers 51 views ### Chromatic number of 2-graph vs hypergraph of point-line incidences Define the chromatic number$\chi(H)$of a (hyper)graph$H$as the smallest$k$such that its vertices can be$k$-colored such that no (hyper)edge is monochromatic. Given a finite set of points$P$in ... • 17.9k 8 votes 0 answers 122 views ### Partial order on graphs induced by homomorphism counts For graphs$F$and$G$, let$\hom(F,G)$denote the number of homomorphisms (adjacency preserving maps) from$F$to$G$. Define a relation$\le_{\hom}$on (isomorphism classes of) graphs as$G \le_{\...
• 1,982
I know the following problem is famous: For a given degree sequence $L$ that is graphic, find an (efficient) algorithm to generate all of the nonisomorphic realizations of $L$. This algorithm is ...
I am looking for references that address lower bounds on the "sphericity" of a graph. For a finite point set in Euclidean $n$-space, if we connect each pair of points by a line segment ...