# Tagged Questions

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

**4**

votes

**0**answers

16 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

29 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

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

**5**

votes

**0**answers

33 views

### Is the recognition of 3DORG in $\mathcal P$?

Problem (Chaplick, Kindermann, Lipp, Wolff):
Is the reconition of 3DORG in $\mathcal P$?
A 2DORG is the intersection graph of rays directed $\to$ or $\uparrow$ in the plane. They can be ...

**5**

votes

**1**answer

224 views

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

Let $n\in\mathbb{N}$ be a positive integer. Two elements of $\{0,1\}^n$ form an edge if and only if their Hamming distance equals $1$. It is known that $\{0,1\}^n$ endowed with this graph structure ...

**2**

votes

**1**answer

109 views

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

I know that many things are known when dealing with random walks on a finite (or even infinite) graph: mixing time, returns to origin, etc. All is based in the use of the Markovian property of such a ...

**4**

votes

**1**answer

84 views

+50

### Component properties in Euclidean graphs with distance threshold

In the context of Euclidean graphs with vertices randomly embedded in either a 2D plane (for instance square with length $L$) or in 3D (similarly, cube of side $L$), where an edge between two given ...

**0**

votes

**0**answers

23 views

### Weak convexity in graphs

I asked the following question in MathStackExchange, but I did not get any answer, and I think that this might be the appropriate venue for the question.
As we know, a finite undirected graph ...

**0**

votes

**1**answer

57 views

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

Let $(X,d)$ be a metric space, and suppose $S\subseteq X$ is a finite subset in which all pairwise distances are distinct (formal definition here).
If $x\in S$ and $k$ is a non-negative integer with $...

**1**

vote

**0**answers

28 views

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

Let $G$ be a Cartesian product of two arbitrary directed weighted graphs $M$ and $N$.
The weights are from a non-commutative finite idempotent semiring.
Do there exist advanced results on the single ...

**3**

votes

**2**answers

240 views

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

Let $G$ be an $n \times n$ grid graph. Is there anything known about the asymptotic growth rate of the number of self avoiding paths from $(0,0)$ to $(n,b)$ (from the lower left corner to some ...

**0**

votes

**0**answers

53 views

### Computer graph question

Let $G$ be an undirected graph containing a cycle $C$. Assuming that every cycle of $G$ has 0 or at least two edges in common with $C$, it true that minimum weight edge of $C$ must be part of a MST (...

**4**

votes

**0**answers

60 views

### equidistributed parameters on graphs

Let $\mathcal G_n$ be the set of (isomorphism classes of unlabelled) simple graphs on $n$ vertices.
I wonder whether there are any 'interesting' combinatorial parameters $a,b: \mathcal G_n\to \mathbb ...

**2**

votes

**2**answers

234 views

### Laplacian of an infinite graph and connected components

For a finite graph with undirected, unweighted edges, a well-known result is that the dimension of the null space of the Laplacian matrix gives the number of connected components. Does this result ...

**1**

vote

**0**answers

55 views

### Walk in the graph induced by a group action

Suppose that graph $G$ is induced by a group $⟨α_1,...,α_r⟩$ acting on a large finite set $X$ for small $r$. To be precise, we have the vertex set $V(G):=X$,
and $x_1x_2\in E(G)$ whenever for some $\...

**4**

votes

**1**answer

192 views

### Understanding proof about chromatic number

Consider an undirected graph $K(n,k,i)$, with the all $k$-element subsets of $\{1,\dots,n\}$ as vertices, and two vertices connected by an edge if their sets intersect in less than $i$ elements.
...

**9**

votes

**1**answer

189 views

### Orientations of Planar Graphs

Let $G$ be a $2$-edge-connected graph drawn in the plane (such that the edges intersect only at the endpoints). I want to orient
the edges of $G$ such that for each vertex $v$, there are no
three ...

**0**

votes

**0**answers

12 views

### Every singular DNN realization of $G$ is completely positive implies

DNN denotes doubly non-negative matrices(both entry wise non-negative and is positive semi-definite). Let $G$ be a Graph.
The following two are equivalent:
(a) Every non-singular DNN realization of $...

**6**

votes

**0**answers

171 views

### $R(3,6) = 18$, especially proving that $R(3,6)>17$

I'm studying the Ramsey numbers, especially $R(3,6) = 18$
I understand that the proof using the theorem $R(m,n) <R(m-1,n)+R(m,n-1)$ can only prove that $R(3,6)<20$. However by Cariolaro's "On ...

**19**

votes

**3**answers

774 views

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

A hypergraph is a pair $H=(V,E)$ where $V\neq \emptyset$ is a set and $E\subseteq{\cal P}(V)$ is a collection of subsets of $V$. We say two hypergraphs $H_i=(V_i, E_i)$ for $i=1,2$ are isomorphic if ...

**5**

votes

**1**answer

194 views

### Blocking $a\to b\to c$ in a DAG with bounded degrees

(This is an (easy-looking) toy question for this one.)
Question. Find the smallest $\alpha$ satisfying the following:
Let $G=(V,E)$ be a finite directed acyclic graph, where each in- and out-...

**0**

votes

**0**answers

25 views

### Is there any closed form/exact formula to count all 4-node subgraphs in a directed graph?

As far as I know, exact/closed form formula for counting all 13 types of 3-node motifs/subgraphs on a directed graph are already known. See reference below.
Helas, I have not found similar result for ...

**11**

votes

**3**answers

464 views

### A Modern Proof of Erdos and Renyi's 1959 Random Graph Paper?

In their paper, Erdos and Renyi consider a random graph with a fixed number of edges, as opposed to the more modern approach of adding each edge independently with probability $p$. From what I ...

**1**

vote

**1**answer

64 views

### $(k,n)$-binary graphs

Let $k\leq n$ be positive integers with $n\geq 2$, and let $[n]=\{1,\ldots,n\}$. Let $V_n=\{0,1\}^{[n]}$ be the set of all functions $f:[n]\to\{0,1\}$, and let
$$E_{k,n} =\big\{\{f,g\}: f,g\in V_n\...

**13**

votes

**1**answer

261 views

### Can the graph of a symmetric polytope have more symmetries than the polytope itself?

I consider convex polytopes $P\subseteq\Bbb R^d$ (convex hull of finitely many points) which are arc-transitive, i.e. where the automorphism group acts transitively on the 1-flags (incident vertex-...

**9**

votes

**1**answer

143 views

### Representations of the automorphism group of graphs via spectral graphs theory

Given a (simple) graph $G=(V,E)$ with $V=\{1,...,n\}$ and let $A$ be its adjacency matrix.
I am interested in the representation theory (over $\Bbb R$) of the automorphism group $\def\Aut{\mathrm{Aut}...

**19**

votes

**2**answers

928 views

### Is it possible that both a graph and its complement have small connectivity?

Let $G=(V,E)$ be a simple graph with $n$ vertices. The isoperimetric constant of $G$ is defined as
$$
i(G) := \min_{A \subset V,|A| \leq \frac n2} \frac{|\partial A|}{|A|}
$$
where $\partial A$ is ...

**1**

vote

**1**answer

57 views

### The Kronecker product of two bipartite graphs' biadjacency matrices: what's it called?

Here's two random $(0,1)$-matrices:
$$
A=
\begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 1 \\
\end{bmatrix}
\qquad
B=
\begin{bmatrix}
1 & 1 \\
0 & 1 \\
\end{bmatrix}.
$$
They can be ...

**6**

votes

**0**answers

74 views

### Combinatorial region-halfplane incidence structures

I've seen a bunch of similar MO questions, yet hopefully this is not a complete duplicate.
Consider $n$ halfplanes in $\mathbb{R}^2$ with their borders in general position, that is, no point of $\...

**2**

votes

**0**answers

99 views

### Space of change of basis matrices between two similar matrices - how to reduce it with additional tests?

Assume we have two real symmetric $n\times n$ matrices: $A, B$. We can easily test their similarity: $\textrm{Tr}(A^k)=\textrm{Tr}(B^k)$ for $k=1..n$. In this case both can be rotated to the same ...

**1**

vote

**0**answers

48 views

### A Random Graph Process

I'd like to understand the following random graph process. I'm not sure if it's difficult or straightforward, so apologies if this is below the level of mathoverflow, but I've gotten no response on ...

**-1**

votes

**1**answer

36 views

### pruning a special graph

You are given a very special graph. The vertices of the graph come in three
columns: left, center, and right. The edges connect vertices from the left to
vertices in the center, and from the center to ...

**0**

votes

**0**answers

13 views

### When is the first blocking flow created in Dinic's algorithm a max flow?

When is the first blocking flow created in Dinic's algorithm a max flow? I understand that this is usually an iterated algorithm where one creates level graphs and augments the existing blocking flow ...

**6**

votes

**0**answers

264 views

### Colored weighted Graphs with only monochromatic perfect matchings

The following purely graph-theoretic question is motivated by quantum mechanics.
Definitions: A bi-colored weighted graph $G(V,E)$ is an undirected graph where every edge is colored, and has a ...

**2**

votes

**1**answer

109 views

### Graphs with exactly $n$ perfect matchings

Is there for every $n\in\mathbb{N}$ a connected, simple, undirected graph $G_n=(V_n,E_n)$ such that $G_n$ has exactly $n$ perfect matchings?

**6**

votes

**0**answers

124 views

### What is known about the distribution of lengths of the cycle you get by adding an edge to a uniform spanning tree?

Let $G$ be a finite, connected graph. Let $T$ be a uniform spanning tree, and let $e$ be a uniformly random edge not in $T$. When we add $e$ to $T$, we get a subgraph with a unique cycle, $C$. I am ...

**0**

votes

**1**answer

75 views

### Connected infinite graphs in which all matchings are “small”

Is there a countable, simple, connected graph $G=(\omega, E)$ such that $\text{deg}(v)$ is infinite for all $v\in \omega$, and for all matchings $M\subseteq E$ the set $V\setminus (\bigcup M)$ is ...

**5**

votes

**1**answer

90 views

### Two graphs with the same number of walks but without a common equitable partition

Consider two undirected graphs $G$ and $H$ of the same order (same number of vertices).
If $G$ and $H$ have a common equitable partition, then it is known (see e.g., Chapter 6 in 1) that these ...

**2**

votes

**0**answers

47 views

### Asymptotic colouring of edges and vertices, and untwisting cocycles

This question regards colourings on edges and vertices on countable directed multigraphs.
We start with an example. Let $G=\mathbb Z^2$. We define two functions $a_h$ and $a_v$ from $\mathbb Z^2 \to \...

**1**

vote

**1**answer

51 views

### monochromatic induced subgraph in a complete 3-partite graph

$H=(V_1\cup V_2 \cup V_3, E)$ is a complete $3$ partite graph such that $|V_1|=|V_2|=|V_3|=n$ . Color the edges with three colors.
My question is: Is it possible to find sets $V_1' \subset V_1, V_2' ...

**0**

votes

**0**answers

72 views

### A series of operations on a graph $G$ to obtain a specific family of subgraphs of $G$

Suppose $G$ is the complete graph on $n$ vertices, do the following operations:
Let $G_0=G$.
Choose one vertex of $G_0$ and let $G_1$ be the subgraph of $G_0$ by taking this vertex away from $G_0$. ...

**3**

votes

**1**answer

73 views

### Maximal matchings in connected graphs

Let $n\in\mathbb{N}$ be a positive integer. Is there a connected graph $G$ such that $G$ cannot be coloured with less than $n$ colours, and every two maximal matchings have non-empty intersection?
(I ...

**2**

votes

**2**answers

100 views

### Graphs in which all maximal matchings intersect

Let $G=(V,E)$ be a simple, undirected graph. A matching is a set $M\subseteq E$ consisting of pairwise disjoint edges. We say $M$ is maximal if it is maximal amongst all matchings in $G$ with respect ...

**0**

votes

**0**answers

25 views

### Search an undirected graph for a path with specified, ordered vertex valencies

Consider an arbitrary finite undirected graph $G = (V,E)$ and a specified finite sequence of vertex valencies or degrees, $\{ d_1, d_2, \ldots d_k\}$, where $k \le O(G)$ (the order of $G$). Is there ...

**4**

votes

**1**answer

316 views

### Mathematical Structure and Objects Induced by Pairs of Disjoint Subsets

Let $\mathcal{S}$ be a finite, discrete and non-empty set, i.e.,
$$\begin{align} \operatorname{card}\left(\mathcal{S}\right) & =:n\in\mathbb{N}^+\\ V& :=\{v\subset\mathcal{S}\ |\ v\ne\...

**7**

votes

**1**answer

250 views

### Number of (distinct) knots with a bounded number of crossings

The title pretty much covers it: are there good (asymptotic) estimates on the number of knot types whose projection has at most $N$ crossings? Similar question with "projection" replaced by "...

**0**

votes

**2**answers

68 views

### Minimize edge number under diameter and max-degree constraint

Given a number n of nodes, a diameter d (d>1) and a max-degree k. Let's assume d and k are chosen such that a graph with n nodes with the desired diameter and max-degree exists.
What is the minimum ...

**0**

votes

**1**answer

55 views

### Find all paths on undirected Graph [closed]

I have an undirected graph and i want to list all possible paths from a starting node.
Each connection between 2 nodes is unique in a listed path is unique, for example give this graph representation:...

**3**

votes

**2**answers

46 views

### Vertex cover number vs matching number

Let $G=(V,E)$ be a finite, simple, undirected graph. A matching is a set $M\subseteq E$ of pairwise disjoint edges. A vertex cover is a set $C\subseteq V$ of vertices such that $C\cap e \neq \emptyset$...

**2**

votes

**0**answers

95 views

### $\mathrm{NP}$-complete problems in graph theory: undirected vs. directed

Is it true that it is much easier to establish $\mathrm{NP}$-complete on undirected graphs than digraphs (directed graph)?
Academic articles proving $\mathrm{NP}$-completeness of problems on ...