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

**7**

**1**answer

### Difference Sets

**7**

**1**answer

### Cycling through the Zeta Garden: Zeta functions for graphs, cycle index polynomials, and determinants

**22**

**8**answers

### Representability of finite metric spaces

**17**

**4**answers

### Can you determine whether a graph is the 1-skeleton of a polytope?

**58**

**9**answers

### What is a continuous path?

**12**

**1**answer

### Different uses of the word “ergodic”

**12**

**4**answers

### How many $p$-regular graphs with $n$ vertices are there?

**16**

**2**answers

### Minimal graphs with a prescribed number of spanning trees

**9**

**1**answer

### Probability of a graph procedure

**3**

**1**answer

### Counting “connected” edge orderings (shellings) of the complete graph [duplicate]

**15**

**2**answers

### Graphs with only disjoint perfect matchings

**0**

**1**answer

### Does this graph contain at least two Hamiltonian cycles?

**37**

**17**answers

### Linear Algebra Proofs in Combinatorics?

**53**

**4**answers

### What is a chess piece mathematically?

**39**

**15**answers

### Strengthening the Induction Hypothesis

**50**

**17**answers

### Generalizations of the Four-Color theorem

**34**

**21**answers

### Generalizations of Planar Graphs

**32**

**18**answers

### Interesting and Accessible Topics in Graph Theory

**52**

**4**answers

### Connectivity of the Erdős–Rényi random graph

**30**

**9**answers

### How many groups of size at most n are there? What is the asymptotic growth rate? And what of rings, fields, graphs, partial orders, etc.?

**22**

**5**answers

### Complete graph invariants?

**28**

**4**answers

### Adjacency matrices of graphs

**12**

**8**answers

### Where on the internet I can find database of graphs?

**39**

**6**answers

### Is it easy to produce hard-to-color graphs?

**27**

**9**answers

### Is the empty graph a tree?

**11**

**2**answers

### Is the Steiner ratio Gilbert–Pollak conjecture still open?

**23**

**2**answers

### Determinants in Graph Theory

**3**

**1**answer

### Can the first non-zero eigenvalue of a Laplacian matrix with more than 1 zero valued eigenvalue be used to reorder an adjacency matrix?

**28**

**3**answers

### Has there been a computer search for a 5-chromatic unit distance graph?

**8**

**2**answers

### Algorithm for embedding a graph with metric constraints

**6**

**3**answers

### Spectrum of orthogonality graph (2)

**5**

**4**answers

### Delaunay triangulations and convex hulls

**23**

**3**answers

### Is every positive integer the permanent of some 0-1 matrix?

**9**

**2**answers

### Graphs with many edges avoided by Hamiltonian cycles

**8**

**2**answers

### Spanning trees of plane graphs containing an edge of every face

**4**

**1**answer

### genus of a finite simple undirected graph

**19**

**3**answers

### Does the hypergraph of subgroups determine a group?

**11**

**1**answer

### Uniquely hamiltonian graphs with minimum degree 4

**9**

**2**answers

### Cubic graphs whose 2-factors all have the same cycle type

**6**

**2**answers

### Heyting algebras originating from directed graphs

**4**

**1**answer

### Graphs with constant edge imbalance

**3**

**1**answer

### Min Bend Orthogonal Knots

**2**

**1**answer

### Proof and interpretation of the following percolation theory result for $n\times n$ square grid

**8**

**2**answers

### Densest Graphs with Unique Perfect Matching

**4**

**2**answers

### Reporting all faces in a planar graph

**4**

**1**answer

### Rigid Strongly Regular Graphs

**2**

**2**answers

### Matching with probabilistic edges

**2**

**1**answer

### Perfect matchings in infinite graphs

**1**

**0**answers

### Possibility of Disconnected Subgraphs of a $k$ Connected $r$ regular Graph under a given condition

**1**

**2**answers