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.

Filter by
Sorted by
Tagged with
0 votes
0 answers
85 views

Turán number of even cycles with diagonal

Let $C_{2k}'$ denote the graph that consists of the cycle on $2k$ vertices and one more edge, a chord connecting two opposite, i.e., distance $k$ vertices of the cycle. What is known about the Turán ...
1 vote
0 answers
77 views

Conditioned random walk over a graph

I want to solve for a conditioned random walk over a graph. I have a directed graph $G$. The random walkers start at a fixed node, Source. They all need to end up at fixed node, Sink. So the random ...
0 votes
0 answers
13 views

Complexity of finding single source paths with capacity constraints and length constraints

Let $G=(V,A)$ be a directed graph with distinguished vertex $s\in V$ and let $c:A\rightarrow{\mathbb N}$ denote arc capacities. For any $t\in V,t\not=s$ we are given two numbers: $C_{t},L_{t}$. Let $...
5 votes
0 answers
113 views

Do uniquely Hamiltonian graphs have cycles of a sufficiently long length?

Let $C$ be a Hamiltonian cycle of a graph $G$. Call an edge $e$ of $G$ a chord if $e\not\in C$. Let each edge of $C$ be weighted $1$ and each chord be weighted $2$. The weight of a path or cycle of ...
1 vote
1 answer
70 views

Algorithmic complexity of calculating maximum weight $k$-regular subgraphs

Question: what is known about the complexity of calculating the heaviest $k$-regular subgraph of a weighted symmetric graph if edge-weights can also be negative? Please note that in contrast to $k$-...
1 vote
0 answers
68 views

(Hyper)Graph canonical labeling - Optimizing for subgraphs [Nauty/Traces?]

To a hypergraph, we can apply the following transformations: [Vertex Removal of Type A] Remove a specified vertex from the hypergraph. As for the edges that contained this vertex, remove all of these ...
15 votes
2 answers
1k views

What is the smallest uniquely hamiltonian graph with minimum degree at least 3?

I would like to know more about uniquely hamiltonian graphs with minimum vertex degree at least 3, and in particular what is the smallest one. (Recall that a graph is hamiltonian if it has a cycle ...
1 vote
0 answers
120 views

On a generalisation of the EKR theorem

Let $n > k >t$ be positive integers, and let us assume $2k \leqslant n$. We denote the set of $k$-subsets of $[n]$ by $\mathcal{F}$. Let $C_1\subseteq \mathcal{F}$ be such that any two elements ...
3 votes
0 answers
136 views

Smallest dominating set

Given a graph $G$, we say $S$ is a dominating set if $S\cup \{N(x):x\in S\}=V(G)$. Let $d(n,k)$ be the smallest integer $s$ so that every $n$-vertex graph $G$ with minimum degree $k$ has some ...
1 vote
0 answers
77 views

Diameters of random bipartite graphs

Given two partite sets of vertices $U$ and $V$ of size $n$. Each vertex in $U$ uniformly randomly selects $K$ ($K$ is a constant and $K\ll n$) vertices in $V$ without replacement and connects a ...
6 votes
1 answer
273 views

Generating 21-vertex 4-regular plane graphs with 8 faces of degree 3 and 15 faces of degree 4

Is there any way to generate all 4-regular plane graphs with 21 vertices, 8 faces of degree 3, and 15 faces of degree 4? If so, how many of these graphs are there and what are they?
1 vote
1 answer
142 views

Refinement of face vectors of the simplicial noncrossing hypertree complexes of McCammond

Einziger on page 65 of "Incidence Hopf algebras: Antipodes, forest formulas, and noncrossing partitions" presents the antipode of a noncrossing partition Hopf algebra as a graded sequence of partition ...
0 votes
1 answer
129 views

Heuristics for lightweighted "cubic" spanning trees

I have the problem of calculating a good approximation of the minimimum-weight spanning tree with vertex-degrees in $\lbrace 1,3\rbrace$ of a complete symmetric graph, without parallel edges or self-...
2 votes
0 answers
56 views

Some version of graph removal lemma

I found the following statement in 'A proof of the stability of extremal graphs, Simonovits’ stability from Szemerédi’s regularity' by Zoltán Füredi: Lemma: For any $\alpha>0$ and a graph $F$, ...
0 votes
0 answers
145 views

Generate all non-isomorphic signed graphs

A signed graph is a graph in which each edge has a plus or minus sign. More specifically, a signed graph is a couple $S=(G, s)$, where $G=(V, E)$ is a graph with vertex set $V$ and edge set $E$, and $...
10 votes
4 answers
2k views

Minimally 2-vertex-connected graphs?

A class of "minimally 2-vertex-connected graphs" - that is, 2-vertex-connected graphs which have the property that removing any one vertex (and all incident edges) renders the graph no longer 2-...
6 votes
0 answers
224 views

Reference to a definition of a graph homology

Let $G$ be a graph, and define $C_k$ to be the free abelian group on the homomorphisms from graphs $H$ such that $K_k$ is a minor of $H$ without needing to do any vertex deletions, only edge ...
1 vote
1 answer
67 views

Lower bound for the sum of the number of vertices of some subgraphs of a directed graph

Let $G$ be any simple weakly connected directed graph with vertices $V$, $\vert V \vert = n$. Let $V_1, \ldots, V_m$, $m = \binom{n}{k}$ be all subsets of $V$ of size $k$. Let $C(V_i)$ be the union of ...
2 votes
1 answer
124 views

Existence of adjacent $a, b$ in a general bipartite graph (with a special degree condition) such that $\frac{\deg(a)}{\deg(b)} \ge \frac{|B|}{|A|}$

Suppose a bipartite graph with two parts $A, B$, for every $b \in B$ we know $\deg(b) \ge 1$. Prove there exists an adjacent $a \in A, b \in B$ such that $\frac{\deg(a)}{\deg(b)} \ge \frac{|B|}{|A|}$.
0 votes
0 answers
30 views

Minimal Non-Symmetric Closed Tracks Under 45-Degree Rotations

Given an arbitrary number of clockwise and anti-clockwise 45-degree track turns, what is the smallest closed track, that is neither axisymmetric nor rotationally symmetrical? For example, AAAAAAAA ...
1 vote
3 answers
501 views

Finding maximum value of degree-3 homogeneous polynomials when variables sum to 1

I would like to be able to find maximum values of degree-3 homogeneous polynomials, when the variables are non-negative real numbers that sum to 1. For example, For example, the maximum value of $xy^...
5 votes
2 answers
425 views

Adjacency matrix of tournament

I met a question in Bondy and Murty’s Graph theory (§1.5.13) The adjacency matrix of a digraph $D$ is the $n \times n$ matrix $\mathbf{A}_D = (a_{uv})$, where $a_{uv}$ is the number of arcs in $D$ ...
2 votes
1 answer
113 views

Convergence of the average weight of an infinite path through a weighted directed graph

Consider a directed graph $G = (V, E, w)$, where $V$ is the set of vertices, $E \subseteq V \times V$ is the set of directed edges (with self-loops allowed), and $w : E \to \mathbb{R}_+$ is a weight ...
0 votes
1 answer
112 views

Spectral characterization of complete or complete bipartite graphs

The Lemma 6 in this paper mention the following spectral characterization of complete or complete bipartite graphs: Let $G$ be a connected graph with $\ge 2$ vertices. Then $\lambda_2=...=\lambda_{n-...
55 votes
21 answers
14k views

Linear algebra proofs in combinatorics?

Simple linear algebra methods are a surprisingly powerful tool to prove combinatorial results. Some examples of combinatorial theorems with linear algebra proofs are the (weak) perfect graph theorem, ...
1 vote
1 answer
85 views

Existence of a strongly regular vertex ordering on cubic graphs

Definition: Let $G=(V,E)$ be a cubic (i.e. $3$-regular) graph, and $<$ a total order on $V$. For $v\in V$ let $v^\downarrow$ denote the set of nodes $w\in V$ such that $w<v$, and let $\alpha(v) =...
5 votes
5 answers
888 views

Two arcs in the complement of a disc must intersect?

Let $D=\{z\in \mathbb C:|z|\leq 1\}$ be the unit disc in the complex plane, with interior $U=\{z\in \mathbb C:|z|<1\}$. Let $A\subset \mathbb C\setminus U$ be an arc intersecting $D$ only at its ...
1 vote
1 answer
65 views

Complexity of calculating the optimal amalgamation of an optimal cycle-cover

Let $G(V,E)$ be a complete symmetric graph with positive edge weights and let further $\mathcal{C}=\lbrace C_1,\,\cdots\,C_k\rbrace$ be the minimum-weight vertex-disjoint cycle cover. The set $E$ of ...
3 votes
1 answer
139 views

Does every graph admit an embedding such that identically-colored edges do not cross?

Given a graph, is it always possible to color the edges of the graph using two colors such that there exists an embedding of the graph in the plane where only opposite-colored edges cross? Simple ...
1 vote
1 answer
44 views

The edit distance from a large complete $p$-partite graph to the Turán graph

Let $K=K(V_1,V_2,\cdots,V_p)$ be a $p$-partite complete graph on $n$ vertices and $T_p(n)$ be the Turán graph. Show that: if $e(K)\geq e(T_r(n))-t$ then $$\sum_{k=1}^p\left(|V_k|-\frac{n}{p}\right)^2\...
2 votes
1 answer
236 views

Do balls in expander graphs have small expansion?

Consider a $d$-regular infinite transitive expander graph $G$, and let $B_r$ be a ball of radius $r$ in $G$. Can one place any upper bounds on the expansion of $B_r$? My intuition is that $B_r$ will ...
2 votes
1 answer
199 views

When is a (co)edge trivial in graph cohomology?

Let $G$ be a connected graph and let $e$ be an edge in this graph. I would like to know if there are necessary and sufficient questions so that $e^{\vee}=0$ in $H^1(G)$? The question must be easy to ...
7 votes
0 answers
223 views

Chip firing on hypergraphs

A (finite) hypergraph is a pair $(V, \mathcal{E})$ where $V$ is a finite set of vertices and $\mathcal{E}\subseteq\mathcal{P}(V)$ with each $E\in\mathcal{E}$ having at least two elements; a ...
17 votes
1 answer
1k views

Which degree sequences are planar graphical?

The Erdős–Gallai theorem characterizes which degree sequences are graphical (i.e. realizable by a simple graph). There has been some work on which degree sequences are planar graphical (i.e. ...
0 votes
0 answers
32 views

Enumeration of flat integral $K_4$

Question: What is known about the enumeration of all $(a,b,c,d,e,f)\in\mathbb{N}^6_+: \\ \quad\operatorname{GCD}(a,b,c,d,e,f)=1\ \\ \land\ \exists \lbrace x_1,x_2,x_3,x_4\rbrace\subset\mathbb{E}^2:\ \...
3 votes
1 answer
2k views

How random are random spanning trees?

Suppose you take a $G(n,p)$ random graph for a fixed probability $p$ and find a spanning tree using Kruskal's algorithm. If you now repeat this process indefinitely, will every tree on $n$ vertices ...
7 votes
1 answer
282 views

The origin of a planar graph theorem of Steinitz and Rademacher

The subsequent statements are extracted from the article titled 'Generating r-regular graphs' (https://doi.org/10.1016/S0166-218X(02)00593-0). A well-known classical theorem of Steinitz and ...
2 votes
1 answer
78 views

"Balanced" separator which is independent set

I am looking for existence results on separators of $r$-regular graphs $G=(V,E)$, which have the property that $S\subset V$ is a separator for all $v,w\in S$ the edge $\langle v,w\rangle\not\in E$ (i....
3 votes
1 answer
119 views

Better solution for an evaluation over a fully connected, symmetric tensor network graph?

I have a somewhat nice approach to the following symmetric network evaluation problem. However, since the result is a possibly elaborate combinatorial problem, that I can not yet solve (edit: which ...
5 votes
0 answers
74 views

Graphs where every maximal clique has the same size

I have a family of (simple, regular, vertex-transitive) graphs and believe that each graph in the family has the property that every maximal clique has the same size. What are some necessary or ...
7 votes
1 answer
231 views

Is the Rado graph the unique countable graph that has all finite graphs as induced subgraphs?

I understand that since the Rado graph is the Fraïsse limit of the class of finite graphs, it is the unique homogeneous graph with this property. Is there another graph not isomorphic to the Rado ...
2 votes
0 answers
62 views

What is the range of connectivity for maximal IC-planar graphs?

A graph is IC-planar if it admits a drawing in the plane with at most one crossing per edge and such that two pairs of crossing edges share no common end vertex. A graph $G$ is maximal in a graph ...
1 vote
1 answer
126 views

Complete minor graphs

Is there any result or known way to find complete minors of graphs? I want to find complete minors of generalized Petersen graphs and $3$-regular graphs. I guess that generalized Petersen graphs $G (n,...
7 votes
1 answer
1k views

Why $K_5$ and $K_{3,3}$?

Most people will have already guessed that this is about Kuratowski's theorem. The theorem states that every non-planar graph must contain a complete graph $K_5$ with five vertices or a complete ...
2 votes
2 answers
189 views

Isometric embeddings of metric $K_{n+1}$ in $\mathbb{R}^n$

Question: is it always possible to embed a complete, symmetric and metric graph $G$ with $n+1$ vertices isometrically in $\mathbb{R}^n$? I'm convinced it must be true, but can't remember having seen ...
0 votes
0 answers
49 views

Kernel perfection in some powers of cycles

Suppose I orient the edges of the power of cycle graph $G=C_n^k$ where $n=16$ and $k=4$ in such a way that all the generated cycles by the elements $1,2,3,4$ are given the standard lexical orientation....
0 votes
0 answers
40 views

Minimal m such that m x K_n is decomposable into disjoint C_3

For a given $n$, is there a way to calculate the minimal value $m$ such that you can decompose the multigraph: $$m \times K_n$$ into disjoint 3-cycles? What about a more general result applied to ...
2 votes
1 answer
143 views

Some identities from graph theory and probability

The other day I attended a seminar about probability. I took some notes and I am now revising it and trying to understand some steps that were omitted by the lecturer. To formulate my question, ...
14 votes
4 answers
733 views

Prove or disprove: $R^{n+1} \supseteq R \cap R^2 \cap \cdots \cap R^n$ for every binary relation $R$ on a set of size $n$

Prove or disprove: $R^{n+1} \supseteq R \cap R^2 \cap \cdots \cap R^n$ for every binary relation $R$ on a set of size $n$. I have verified the statement for $n \leq 4$ with a Mathematica code. I have ...
6 votes
0 answers
720 views

Tensor product of quivers

As a special case of a general construction I have constructed "accidentally" a tensor product of quivers aka directed multigraphs (aka directed graphs for category theorists). Probably this ...