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.
5,150
questions
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 ...