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,147
questions
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 ...
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:\ \...
7
votes
1
answer
281
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 ...
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 ...
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\...
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 ...
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 ...
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 ...
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....
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 ...
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
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, ...
2
votes
0
answers
135
views
Generalizing Hall's marriage theorem to non-perfect matchings
Let $G = (X, Y, E)$ be bipartite graph such that $|X|=|Y|=n$.
A matching $M \subseteq E$ is a subset of disjoint edges
(i.e., there does not exist a pair of edges $(x, y) \in M$ and $(x', y') \in M$ ...
0
votes
0
answers
30
views
connected graphs with largest eigenvalue greater than 2
I work on a variation of the dollar game. This game is known to end after a finite number of firing iff the graph is a Smith graph. These graphs are also known as the famous and ubiquitous ADE graphs (...
0
votes
0
answers
35
views
Consider the probability of connecting the terminal vertices using Binary Decision Diagram with length constraint
Definitions
Given an undirected graph $G=(V,E,p),p:E \to [0,1]$ where $V$ is the set of vertices, $E$ is the set of edges and $m=|E|$, and $p$ represents the probability that an edge functions. A set ...
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 ...
0
votes
0
answers
125
views
Approximating all spanning trees with their sample
In a complete graph with $n$ vertices there are $n^{n-2}$ trees.
In my research I'm analyzing trees in the following way (each edge has a weight):
Get a tree.
Build a complete graph, by the following ...
2
votes
2
answers
225
views
Finding an easy example applying the general Lovász local lemma
Is there any easy application for the general local lemma as follows? If someone knows, please tell me the references or just post an example here. Thanks.
General Lovász local lemma: Consider a set $...
3
votes
0
answers
97
views
Is every finite metric space representable in a pseudo-Euclidean space?
Let $X$ be a finite set with a (true) metric $d$ and $|X| = n$. Does there exist a set $Y$ of $n$ points in $R^n$ with a pseudo-Riemannian metric with signature $(n - k, k, 0)$ for some integer $k$ ...
2
votes
0
answers
229
views
Injection of Catalan objects into 3-connected planar graphs
Let $C_n = \frac{1}{n+1}\binom{2n}{n}$ be the $n$-th Catalan number, counting, for example, the number of (rooted) triangulations of the $(n+2)$-gon.
Let $P_n$ be the number of three-connected planar ...
0
votes
0
answers
71
views
Bramble with order 5 for the Wagner graph
For treewidth $3$, there are four forbidden minors: K5, the graph of the octahedron, the pentagonal prism graph, and the Wagner graph.
This implies that the Wagner graph should have tree-width at ...
2
votes
0
answers
84
views
Constructing Hamiltonian circuits in acyclic digraphs
Any directed graph $G$ lacking cycles can acquire a Hamiltonian circuit through the addition of a sufficient number of edges.
Q. Is there a method to minimize the addition of edges to achieve a ...
7
votes
4
answers
746
views
Random sample of spanning trees
In a complete graph with $n$ vertices there are $n^{n-2}$ spanning trees.
I want to get a random sample of size $k$ from the set of all spanning trees.
The most basic and naive idea is to generate all ...
4
votes
0
answers
104
views
Graphs and symmetries
Let us define a symmetric cut of the graph as a cut which cuts the graph into two isomorphic graphs and that the cut preserves the isomorphism i.e. the edges that are cut only connect vertices that ...
4
votes
1
answer
200
views
Erdős–Rényi random graphs — reproducing 2 inequalities
In Erdős and Renyi's 1959 paper On random graphs I
, I'm trying to reproduce, starting from Eq.\eqref{1} in their paper, the two inequalities that appear in Eq.\eqref{2}.
Eq.\eqref{1} is:
$$
P \le \...
2
votes
0
answers
73
views
Minimum cost k-edge connected subgraph
The problem of finding a k-edge connected spanning subgraph with the minimum number of edges is $ \mathcal{NP} $-hard in general. Is it the case for positive weighted graphs with "fractional ...
1
vote
1
answer
98
views
Non-isomorphic walk-regular graphs with the same number of closed walks at any length
Are there known examples of couples of non-isomorphic walk-regular graphs with adjacency matrix $A_1$ and $A_2$ and such that $(A_1^k)_{i,i} = (A_2^k)_{i,i}$ for all $k \gt 0$?
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-...
2
votes
1
answer
55
views
NP-hardness of vertex cover for 3-chromatic graphs
Is the vertex cover problem remains NP-hard for 3-chromatic graphs?
I am almost certain it is, but was unable to find a reference.
Thanks.
1
vote
0
answers
75
views
Graph product which produces a graph with girth of one of the input graphs and minimum degree of the other
I was wondering if there is a known graph product which takes graphs $G$ and $H$ and produces an output graph with the girth of $G$ but the minimum degree of $H$?
Kind of like zigzag product which ...
2
votes
1
answer
133
views
Prove $G$ is regular if $d(u, v)$ is $x$ for adjacent $u$ and $v$ and is $y \ge 2$ otherwise
Prove $G$ is regular if $d(u, v)$ is $x$ for adjacent $u$ and $v$ and is $y \ge 2$ otherwise.
Here $d(u, v)$ denotes the number of common adjacent vertices between $u$ and $v$.
PS: I've been working ...
5
votes
1
answer
216
views
Eulerian trails in complete graphs
Assume that for some odd $n$ we have a complete graph $K_n$. Is it possible to always find Eluerian trail on $K_n$ such that if we have visited vertices $axb$ then we never before nor after visit $ayb$...
5
votes
0
answers
79
views
When does the ΔY-family of a simple graph contain multigraphs?
Given a graph $G$, its ΔY-family is the smallest family of graphs that contains $G$ and is closed under ΔY- and YΔ-transformations.
Since YΔ-transformations can introduce multi-edges, the ΔY-family of ...
4
votes
0
answers
131
views
Does a critical graph have to be product-irreducible?
A finite, simple, undirected graph $G=(V,E)$ is said to be (vertex-)critical if for all $v\in V$ we have $\chi(G\setminus\{v\}) < \chi(G)$.
Let me add that in this context, $\chi(\cdot)$ denotes ...
1
vote
1
answer
210
views
About a result by P. Erdős and H. Sachs on graph with large girth
I recently came across the following result:
For any integers $d,r\geq 2$ and $n\geq 4d^{r(d+1)}$, there is a $d$-regular graph on $n$ vertices with girth at least $(d+1)r+1$.
referring to
"P. ...
1
vote
0
answers
105
views
$K_0$ of finite graphs
We have two operations on finite graphs, first the disjoint union and the categorical product. I want to use these operations to associate a r(i)ng $R$ to finite graphs. An element of that ring is an ...
0
votes
1
answer
114
views
Product decomposition for finite graphs
We say that a finite, simple, undirected graph $G = (V,E)$ is (product-)irreducible if it is connected and there are no graphs $A,B$ such that $G\cong A\times B$ (where $\times$ denotes the ...
1
vote
0
answers
45
views
Bounds on the spectral radius of a perturbed directed graph
Suppose $(G_n)$ is a sequence of strongly connected directed graphs (without multiple edges) with $G_n$ having $n$ edges such that the adjacency matrix $A_n$ of $G_n$ is primitive, and let $(G_n’)$ be ...
1
vote
1
answer
197
views
Connected vertex-transitive graphs of fixed chromatic number and arbitrary size
A simple, undirected graph $G=(V,E)$ is said to be vertex-transitive if for all $v,w\in V$ there is a graph isomorphism $\varphi:V\to V$ such that $\varphi(v) = w$.
The cyclic graphs $C_{2n+1}$ are ...
0
votes
0
answers
55
views
Finding small connected subgraphs of a random regular graph
Fix parameters $m,f,b$. I do not believe it matters for the general form of the question, but in the problem I am examining $m,f,b$ are all powers of $2$ with $m \gg f > b$. For example $m=2^{25},f=...
4
votes
1
answer
119
views
Longest paths and cycles in Steiner triple systems
A Steiner triple system is a 3-uniform hypergraph in which every pair of vertices is contained in exactly one edge. A linear cycle (also called loose cycle) length $t$ consists
of $2t$ cyclically ...
3
votes
1
answer
227
views
Are "ultra-regular" bipartite graphs complete?
Let $X, Y$ be non-empty, disjoint sets and let $R\subseteq X\times Y$ be a binary relation. For $x\in X$, we set $R(x) = \{y\in Y: (x,y) \in R\}$ and for $y\in Y$, let $R^{-1}(y) = \{x\in X:(x,y)\in R\...
0
votes
0
answers
71
views
An $n$-dimensional generalized Hoffman’s circulation theorem?
For a directed graph $G$, a 1-dimensional circulation is a function $f:E(G)\rightarrow \mathbb{R}$ such that for every $v\in V(G)$,
$$\sum_{uv\in E(G)}f(uv)=\sum_{vw\in E(G)}f(vw),$$
where $uv$ is an ...
5
votes
2
answers
749
views
How to effectively search Internet for graphs not for function graphs? [closed]
So, is there any way to distinguish graphs and plots in Internet?
I was looking for (Olivier-)Ricci curvature of graphs and found a lot about Ricci curvature of function graphs and not so much about ...
0
votes
0
answers
35
views
Decompose bipartite graph by integer flow
Given a bipartite graph $G$ with sides $A,B$.
A method to decompose the edge-set of $G$ into two subgraphs $G_1,G_2$ subject to some constraints is to add two extra vertices, direct the edges from $A$ ...
8
votes
1
answer
207
views
Is there a bipartite graph with $\sqrt{2}$ as an eigenvalue with high multiplicity, specifically more than in the Heawood graph?
The Heawood graph is a $3$-regular graph on $14$ vertices. Its (adjacency) spectrum is $\{ (3)^1, (\sqrt{2})^6, (-\sqrt{2})^6, (-3)^1 \}$. So, $3/7 \approx 42.8\%$ of its eigenvalues equal $\sqrt{2}$.
...
1
vote
1
answer
208
views
Qualitative values between two electrons in an atom or how to interpret these values?
This question is a little bit trying to understand physics through geometry of simplex:
Let $E_{i,j}$ be the ionization energy in times the number of hydrogen ionization energy for an element with ...
1
vote
1
answer
161
views
Who introduced the concept of beyond planar graphs?
The concept of planar graphs seems to be standard (I'm also not sure who first used this term), and recently, beyond planar graphs attract a lot of interest in the field of graph drawing. I know that ...