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

vote

**0**answers

10 views

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

Our problem is as follows:
NEARLY-EQUAL-CYCLE-PAIR
Input: An undirected graph $G(V,E)$
Output: YES if there exists $2$ (simple) cycles in $G$ which lengths differ by $1$, otherwise NO
Is ...

**4**

votes

**1**answer

40 views

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

Since deciding whether a graph contains a Hamiltonian cycle is $NP$-complete, the counting problem which counts the number of such cycles of a graph is $NP$-hard.
Is it also $PP$-hard in the sense ...

**-1**

votes

**1**answer

69 views

### Existence of a graph with strong restrictions

Given a maximal degree $k$ and maximal diameter $d$. We identify 3 nodes, $i$, $j$, and $v$. Can an undirected graph exist, such that:
all nodes but $v$ have full degree $k$ ($v$ having a lower ...

**4**

votes

**1**answer

53 views

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

The odd girth of a graph $G$ is defined as the minimum length of an odd cycle in $G$. Let $n_g(k)$ denote the minimum number of vertices in a $k$-chromatic graph of odd girth $g$. What are the known ...

**2**

votes

**1**answer

33 views

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

Suppose $G=(V,E)$ is a connected graph and $T=(V_T, E_T)$ is a subgraph of $G$ that is a tree.
If we further suppose that any pair of vertices $v,w \in V_T$ that are not joined by a single edge in $...

**2**

votes

**0**answers

74 views

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

Let $G$ be an acyclic directed graph with $MN$ vertices arranged into $M$ generations of $N$ vertices each. We stipulate that edges may only go from generation $j$ to generation $j+1$, so there are $(...

**1**

vote

**1**answer

25 views

### Algorithm for cliques in weighted graph

Is there a known algorithm (besides brute force) for the following problem:
We have given an edge-weighted complete graph $G$ and a finite set of natural numbers $A = \lbrace n_1,\ldots,n_k \rbrace$ (...

**3**

votes

**0**answers

58 views

### Maximum spanning paths in a graph

Is there any research on the question of finding a spanning subgraph in the form of a collection of independent paths with a maximum number of edges? If the paths are simply edges we have the maximum ...

**7**

votes

**1**answer

149 views

### Counting spanning trees of a planar graph

I know through Kirchoff's Theorem, one can calculate the number of spanning trees via the determinant of a Laplacian. This has complexity $O(N^{2.373}$). I was wondering if anyone was aware of a ...

**1**

vote

**0**answers

30 views

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

I am interested in finding the best expansion parameters for unbalanced left-regular expander graphs.
Specifically, fix $\delta\in(0,1/2)$, and a positive integer $d$. Let us call a bipartite graph $\...

**8**

votes

**0**answers

111 views

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

A colouring of edges of a graph is distingushing if no non-identity automorphism of the graph preserves this colouring.
Problem. Is it true that each biconnected graph possesses a distinguishing ...

**0**

votes

**0**answers

47 views

### Bijective operations on finite simple graphs

Let $\mathcal G_n$ be the set of (isomorphism classes of unlabelled) simple graphs on $n$ vertices.
I am interested in specific bijective maps $\mathcal G_n\to\mathcal G_n$, defined for all $n$. An ...

**5**

votes

**0**answers

61 views

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

Conjecture (Csóka-Lippner-Pikhurko). If $G$ is a graph with each vertex of degree $\le d$ with at most $d-1$ pendant edges properly coloured, then this pre-colouring can be extended to all edges of $G$...

**0**

votes

**0**answers

44 views

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

Suppose $T$ is a ternary tree with $s$ nodes. Here, a tree is ternary if every node in the tree is either a leaf node (with no child) or a non-leaf node with exactly three child. See below for a ...

**0**

votes

**0**answers

12 views

### Making a Graph Eulerian for Applying TSP Heuristics

To rule out isolated vertices, let a graph be called Eulerian, if a tour exists, on which every vertex is encountered at least once and, in which every edge is traversed exactly once.
That definition ...