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

**2**

**1**answer

### Asking for an example of a graph $G$ satisfying the following property

**4**

**1**answer

### The existence of a specific kind of independent set in a connected graph satisfying the following property

**7**

**1**answer

### Grinberg's uniquely hamiltonian 3-connected graphs (Russian paper)

**1**

**0**answers

### Complex of graphs with domination number greater than k

**1**

**0**answers

### Percolation and diameter of graph

**1**

**1**answer

### Walks of odd Lengths in a Matrix

**0**

**1**answer

### Standard names of two finitary properties of hypergraphs?

**12**

**1**answer

### Is each cover of the plane by lines minimizable?

**1**

**1**answer

### Optimal Graph Splitting

**3**

**0**answers

### Halin Graphs with Highest Number of Hamilton Cycles

**15**

**3**answers

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

**7**

**1**answer

### Two disjoint trees

**0**

**0**answers

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

**7**

**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

**34**

**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?

**5**

**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?

**9**

**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**

**3**answers

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

**1**

**2**answers

### Bipartite subgraphs with lots of edges

**3**

**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

**3**

**1**answer

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

**5**

**1**answer

### Domination numbers of infinite graphs

**3**

**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

**4**

**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