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

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

### A permutation problem

**1**

**0**answers

### An “almost separable” optimization problem on a graph

**1**

**0**answers

### Family of rooted trees parameterized by binary sequences

**2**

**1**answer

### On the laplacian of connected, undirected, multigraphs without loops

**3**

**2**answers

### Computer program for counting graph homomorphisms

**0**

**0**answers

### Fixed paths in Menger's Theorem

**1**

**0**answers

### Bipartite clustering is NP-hard?

**16**

**0**answers

### Straight-line drawing of regular polyhedra

**2**

**1**answer

### Minimal cutting sets in connected graphs

**0**

**2**answers

### Is there a standard name for this type of multidigraph?

**4**

**1**answer

### Why is the number of Hamiltonian Cycles of n-octahedron equivalent to the number of Perfect Matching in specific family of Graphs?

**7**

**0**answers

### A question related to Conways 99 graph problem

**4**

**1**answer

### Citations graphs what is known?

**9**

**1**answer

### Are bipartite Moore graphs Hamiltonian?

**0**

**0**answers

### Is this Graph Iteration Already Known?

**1**

**0**answers

### Juggling the Jacobi identity

**0**

**1**answer

### Large complete minors of $\mathbb{Z}^\omega$

**11**

**3**answers

### Cops, Robbers and Cardinals: The Infinite Manhunt

**1**

**1**answer

### Non hamiltonian k-regular bipartite graphs

**0**

**1**answer

### Complete minors of the grid graphs $\mathbb{Z}^n$

**0**

**0**answers

### Calculation of Vertex Weights for Combinatorial Optimization of Regular Spanners

**1**

**1**answer

### Probability for a group of stones to live on an infinite Go board

**2**

**1**answer

### Conditions for a matrix to be a Graph Laplacian [closed]

**8**

**1**answer

### Graphs with only disjoint perfect matchings, with coloring

**2**

**0**answers

### What is known about “graph algebras”?

**4**

**0**answers

### Separating stars and large intersections of cycles

**-1**

**2**answers

### On a condition concerning the number of neighbors in bipartite graphs

**1**

**0**answers

### Is the partition of bipartite graphs NP-hard?

**2**

**0**answers

### Size of the last non-empty $k$-core of a random graph

**6**

**0**answers

### What is the smallest number of vertices in a graph whose every orientation contains a directed straight path of length 3

**1**

**1**answer

### The minimum possible degree of a graph of $n$ vertices, in which all pairs of nodes have a distance no more than $d$

**2**

**2**answers

### Injective, but no bijective neighborhood map

**0**

**0**answers

### Complexity of Minimum Spanning Trees with Lower Degree Bounds

**1**

**1**answer

### Existence of dense graph with relatively small codegree?

**7**

**2**answers

### complicated combinatorial algorithms with good descriptions

**0**

**1**answer

### Description of Linear Time Algorithm for TSP in Halin Graphs

**0**

**1**answer

### Degree Distribution of Planar Minimum Spanning Trees

**0**

**1**answer

### Maximum partition of bipartite graph

**1**

**2**answers

### Extremal density of a graph without a non-backtracking $2k$-cycle

**3**

**0**answers

### Number of hypercube unfoldings

**3**

**0**answers

### Growth models with lookahead

**7**

**1**answer

### A Question on Graph Limits

**3**

**0**answers