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

**1**

**0**answers

### Halin Graphs with Highest Number of Hamilton Cycles

**12**

**2**answers

### Can we realize a graph as the skeleton of a polytope that has the same symmetries?

**4**

**1**answer

### Two disjoint trees

**0**

**0**answers

### Name for Spanning Trees Containing all Edges of a Minimum Weight Perfect Matching

**4**

**0**answers

### Partitioning the vertices of a graph into induced trees

**1**

**0**answers

### The number of Laplacian eigenvalues of a graph in interval [k,n]

**5**

**1**answer

### Counting promenades on graphs

**1**

**0**answers

### Matchings in infinite, not necessarily bipartite, graphs

**5**

**1**answer

### Why is the number of Perfect Matchings in a triangular grid equivalent to the number of Royal Paths?

**6**

**1**answer

### Smallest set of nonzero vectors in $\mathbb F_2^n$ which intersects every 2-dimensional subspace

**2**

**2**answers

### Random walk and isoperimetric constant

**1**

**1**answer

### A weaker version of Dirac's theorem

**4**

**1**answer

### Can the bramble number and the strict bramble number of a graph be equal?

**3**

**0**answers

### Hadwiger number of Erdös-Faber-Lovasz graphs

**32**

**2**answers

### How to find Erdős' treasure trove?

**5**

**1**answer

### “König's theorem” for $T_2$-spaces?

**2**

**0**answers

### Can Orientability of Manifolds be Generalized to TSP Instances?

**4**

**1**answer

### Cayley graph properties

**0**

**0**answers

### Why do middle roots of the $\chi(p)$ graphs and percolation thresholds vary linearly with diagonal probability $q$ (in large random binary matrices)?

**2**

**1**answer

### Generalization: (The “number” of) smaller sized clusters in large random binary matrices follow a descending order. Why?

**3**

**1**answer

### Why is number of single cell clusters always greatest in a random matrix?

**-2**

**0**answers

### Help with graph theory

**8**

**2**answers

### Counting Hamiltonian cycles in $n \times n$ square grid

**2**

**1**answer

### Is a simple graph matrix the sum of a “shiftordered” matrix and its transposed matrix

**4**

**2**answers

### Is a simple graph the “sum” of a partial order and its dual?

**1**

**2**answers

### Bipartite subgraphs with lots of edges

**2**

**1**answer

### Concentration of measure in graph theory

**1**

**0**answers

### Can we efficiently count modulo 2 the number of connected subgraphs of a planar graph?

**2**

**1**answer

### Local-Global Principle in Graph Spectrum

**2**

**1**answer

### Infinite graph with lots of non-isomorphic induced subgraphs

**5**

**1**answer

### Domination numbers of infinite graphs

**2**

**0**answers

### Reference request: Bipartite symmetric graphs are hamiltonian

**8**

**1**answer

### Does Vizing's conjecture hold for the infinite graphs?

**9**

**1**answer

### Finite group representation as $\mathrm{Aut}(\Gamma)$ action $H^1(\Gamma,\mathbb{Z})$ of graph?

**0**

**0**answers

### Hopcroft-Karp Algorithm

**3**

**2**answers

### Is there an efficient way to represent all non-simple cycles of a digraph up to the number of vertices?

**15**

**1**answer

### Chromatic numbers of infinite abelian Cayley graphs

**3**

**1**answer

### Inertial decomposition of graphs

**1**

**1**answer

### Infinite connected $k$-regular graphs

**3**

**2**answers

### Distance regular Cayley graphs on $Z_2^n$?

**0**

**0**answers

### Edge coloring, with a special condition

**1**

**1**answer

### Infinite connected graphs isomorphic to their line graph

**15**

**2**answers

### Labeling binary trees so that adjacent vertices differ by a power of two

**3**

**2**answers

### Orientability of $\mathbb{Z}^n$

**1**

**0**answers

### $\exp(-Cn^{\epsilon})$ estimate for probability of Brouwer-Haemers condition in Erdos-Renyi-like random graph

**2**

**1**answer

### When does a row standardized adjacency matrix have a real spectrum?

**1**

**0**answers

### Characterization of k-walk-equivalent graphs

**2**

**0**answers

### On the frequency with which a vertex can be added to the independent sets in a graph

**2**

**1**answer

### $\omega$-Hamilton paths in $\mathbb{Z}^n$

**6**

**1**answer