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
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 ...
user3521569's user avatar
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 ...
divergent's user avatar
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:\ \...
Manfred Weis's user avatar
  • 12.6k
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 ...
L.C. Zhang's user avatar
  • 1,605
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 ...
Noah Schweber's user avatar
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\...
Zeta's user avatar
  • 13
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 ...
doogrammargood's user avatar
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 ...
L.C. Zhang's user avatar
  • 1,605
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 ...
Vilhelm Agdur's user avatar
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....
vidyarthi's user avatar
  • 2,007
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 ...
D.S. Lipham's user avatar
  • 3,055
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 ...
Manfred Weis's user avatar
  • 12.6k
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 ...
Sebastian's user avatar
  • 101
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, ...
MathMath's user avatar
  • 1,255
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$ ...
errorist's user avatar
  • 121
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 (...
Gianfranco's user avatar
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 ...
caaaaaat's user avatar
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 ...
Geoffrey Critzer's user avatar
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 ...
Paul R's user avatar
  • 39
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 $...
Xin Zhang's user avatar
  • 1,130
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$ ...
Steve Riley's user avatar
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 ...
Martin Rubey's user avatar
  • 5,533
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 ...
Mark Chimes's user avatar
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 ...
ABB's user avatar
  • 3,898
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 ...
Paul R's user avatar
  • 39
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 ...
superriemann's user avatar
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 \...
RickB88's user avatar
  • 43
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 ...
Bence's user avatar
  • 21
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$?
Fabius Wiesner's user avatar
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-...
YuiTo Cheng's user avatar
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.
Yevgeny Levanzov's user avatar
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 ...
kreitz's user avatar
  • 53
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 ...
Nima Aryan's user avatar
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$...
Todor Antic's user avatar
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 ...
M. Winter's user avatar
  • 12.5k
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 ...
Dominic van der Zypen's user avatar
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. ...
Isomorphism's user avatar
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 ...
HenrikRüping's user avatar
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 ...
Dominic van der Zypen's user avatar
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 ...
a person's user avatar
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 ...
Dominic van der Zypen's user avatar
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=...
smarky's user avatar
  • 1
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 ...
X. Li's user avatar
  • 373
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\...
Dominic van der Zypen's user avatar
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 ...
Connor's user avatar
  • 251
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 ...
zroslav's user avatar
  • 1,412
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$ ...
Connor's user avatar
  • 251
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}$. ...
The Amplitwist's user avatar
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 ...
mathoverflowUser's user avatar
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 ...
L.C. Zhang's user avatar
  • 1,605