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

**0**

**2**answers

### Vertex Connectivity of the Hypercube [closed]

**7**

**1**answer

### Going up of an amalgamated decomposition of a subgroup of finite index

**4**

**1**answer

### existence of a certain subset of vertices in a graph

**0**

**2**answers

### Does Max Flow produce uniform results? [closed]

**0**

**1**answer

### Minimizing the set of “wrong” edges in $K_\omega$ with $\{0,1\}$-weights

**1**

**0**answers

### Generate all connected non-isomorphic graphs of n vertices modulo local complementation?

**1**

**0**answers

### matching two positive-semidefinite matrices

**1**

**0**answers

### What is intuitive perception of $T_{\alpha_1} \circ T_{\alpha_2} \circ … \circ T_{\alpha_M} $ in graph domain?

**10**

**1**answer

### An upper bound for the largest Laplacian eigenvalue of a graph in terms of its diameter

**1**

**1**answer

### Number of sequences of edges that contain at least one subsequence which is a walk between vertex $i$ and $j$

**2**

**2**answers

### Clique Size in “Triangle Regular” Graphs

**11**

**0**answers

### Quantitatively characterizing the failure of the converse of Dirac's theorem

**9**

**1**answer

### Discrete Pin structures

**-1**

**0**answers

### Babai Invariant group

**3**

**1**answer

### Minimal vertex cover

**2**

**1**answer

### Upper bound on the number of induced subgraphs of the square lattice with all degrees even

**3**

**1**answer

### Cliques in Cayley graph on $n$-cycles

**0**

**0**answers

### Equitable partition

**0**

**1**answer

### Graph with at most 2 degrees of separation between every node, but minimal average degree

**7**

**1**answer

### Given any finite relation $R$ what is the cardinality of $\langle R\rangle=\{\underbrace{R\circ R\cdots \circ R}_{n\text{ times}}:n\in\mathbb{N}\}$?

**5**

**0**answers

### Universal point sets for 1-plane graphs

**6**

**0**answers

### A conjecture on the coefficient of a special term in the expansion of the graph polynomial?

**1**

**1**answer

### Degree sequence along an Eulerian cycle

**3**

**1**answer

### Typical labelled vs. unlabelled trees properties

**5**

**1**answer

### Length minimizing graphs between a finite set of points

**3**

**1**answer

### Optimal Strategies for a “Blind” Graph Coloring Game

**3**

**0**answers

### Karp hardness of two cycles which lengths differ by one

**6**

**1**answer

### What is the complexity of counting Hamiltonian cycles of a graph?

**-1**

**1**answer

### Existence of a graph with strong restrictions

**4**

**1**answer

### Minimum number of vertices in a $k$-chromatic graph of odd girth $g$

**2**

**1**answer

### Terminology for tree subgraphs where non-neighbouring vertices are not connected by single ambient edges

**2**

**0**answers

### Percolation-type question involving phase transition for graded acyclic directed graph

**1**

**1**answer

### Algorithm for cliques in weighted graph

**3**

**0**answers

### Maximum spanning paths in a graph

**7**

**1**answer

### Counting spanning trees of a planar graph

**1**

**0**answers

### Tight upper and lower bounds for unbalanced left-regular expander graphs

**8**

**0**answers

### Minimal number of colours in distinguishing colouring of biconnected graphs

**4**

**4**answers

### Bijective operations on finite simple graphs

**5**

**0**answers

### Extending colouring of graphs using small number of colours

**0**

**0**answers

### How many possible choices are there to make a ternary tree equal height by inserting nodes?

**6**

**0**answers

### Does the problem of recognizing 3DORG-graphs have polynomial complexity?

**5**

**1**answer

### Are Gray codes in $\{0,1\}^n$ isomorphic?

**2**

**1**answer

### non-backtracking random walk in regular (finite) graphs

**4**

**1**answer

### Component properties in Euclidean graphs with distance threshold

**1**

**0**answers

### Weak convexity in graphs

**0**

**1**answer

### Graphs represented by a subset of a metric space

**1**

**0**answers

### Single source shortest path over non-commutative finite idempotent semiring in Cartesian product

**3**

**2**answers

### Number of self avoiding paths on a grid graph?

**7**

**1**answer

### equidistributed parameters on graphs

**2**

**2**answers