Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
2answers
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
0answers
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
0answers
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
2answers
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
3answers
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
1answer
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
0answers
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
3answers
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
1answer
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
1answer
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
1answer
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
2answers
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
2answers
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
0answers
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
1answer
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
1answer
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
2answers
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
1answer
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
2answers
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
0answers
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 ...