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
10
views
Structural description of a particular set motivated by graph reconstruction
$\DeclareMathOperator\Coh{Coh}\DeclareMathOperator\Sym{Sym}\DeclareMathOperator\Aut{Aut}$In this post, I asked a question regarding a particular function $\psi$ whose construction is motivated by the ...
0
votes
0
answers
18
views
Does this "linear-approximated" version of Graph Counting Lemma hold?
Let $0\leq d\ll\varepsilon,\frac{1}{e},\frac{1}{v}\leq 1.$ Let $G$ be a $n$-vertices graph ($n$ is sufficient large, $1/n\ll d$) and for any $A,B\subseteq V(G)$, the edge density $d(A,B)\geq d.$ Then ...
0
votes
0
answers
19
views
Are there 4-connected planar non-hamilton multi-graphs?
Tutte proved the famous result: Every planar 4-connected graph has a hamiltonian cycle. But I read in Section 111.6.5 on book Eulerian Graphs and Related Topics that the author Herbert Fleischner ...
0
votes
0
answers
25
views
Set of enclosed convex polyhedra in a graph
Given a straight-line graph embedded in $\mathbb{R}^3$ with known vertex coordinates and edges and no edge intersections, is it possible to find all the enclosed convex polyhedra inside? If so, is ...
1
vote
1
answer
114
views
Chromatic number of the insert-and-shift graph on $S_n$
Let $S_n$ be the collection of bijections $\varphi:\{1,\ldots,n\}\to \{1,\ldots,n\}$. In an earlier question, the insert-and-shift graph structure was introduced on $S_n$ and the resulting graph is ...
0
votes
0
answers
23
views
Is there a variant of the crossing lemma for multigraphs with arbitrary embedding?
Suppose $G$ is a graph with $m=|E(G)|$ edges and $n=|V(G)|$ vertices.
Suppose $sim(G)$, the simplification of $G$ contains $ m' >> 3n $ edges.
Call the set of edges corresponding to an edge $uv$...
4
votes
1
answer
243
views
A question related to "Locally Sidorenko" type problem
Let $F$ be a bipartite graph and $\delta_F=\delta(F)$ be a constant. Let $p\geq 0$ be a given constant.
Let $W$ be a graphon with $\int W=p$ and for any $A,B\subseteq \left[0,1\right]$ with $|A|,|B|\...
2
votes
0
answers
74
views
"separators" for nonplanar graphs embedded in the plane
Given a nonplanar graph $G$ drawn in the plane with crossings.
Does there exist a small subset $S$ of edges of $G$ such that after the removal of all edges that intersect or share an endpoint of an ...
0
votes
1
answer
80
views
Homology of independence complex after removing a vertex
Let $G$ be a chordal graph, $I(G)$ be its independence complex, and $v \in V(G)$ be a simplicial vertex (that is, $v$'s neighborhood is a clique).
Is there a way to relate the homology of $I(G)$ and ...
0
votes
0
answers
30
views
Asymptotic bound on the number of simple connected graphs of bounded degree
I have posted this question on Mathematics, but unfortunately no luck so far.
Let $\mathcal{G}$ be the family of simple connected graphs on $n$ vertices, where each graph has more than $m$ edges, and ...
1
vote
0
answers
51
views
A generalized/set hamiltonian cycle problem on directed graphs
So this problem originally stems from the asymmetric generalized/set TSP problem, where I am interested in asking the question which or how many edges I can delete while maintaining feasability. The ...
0
votes
0
answers
16
views
Bound the $\infty$-norm of the eigenvector of the second minimum eigenvalue of normalized Laplacian from below
I meet the above problem while reading a paper. The problem can be stated as below.
Consider an undirected graph $G$. Let $\mathbf{v}$ be a vector such that $\mathbf{D}^{1/2}\mathbf{v}$ is the ...
2
votes
1
answer
220
views
Why do we get a connected 2-regular graph?
In reading "PUBLIC-KEY CRYPTOSYSTEM BASED ON ISOGENIES" by Rostovtsev and Stolbunov, they claim on page 8 that the set $U=\{E_i(\mathbb{F}_p)\}$ of elliptic curves with a specific prime $l$ ...
1
vote
0
answers
40
views
If $G$ is a connected bipartite graph, then the edge ideal $I(G)$ is normally torsion free
I am studying the paper "On the Ideal Theory of Graphs" by Simis, Vasconcelos and Villarreal, Journal of Algebra 167, No. 2, 389-416 (1994), MR1283294, Zbl 0816.13003. I got stuck at theorem ...
2
votes
1
answer
130
views
Do the dual graphs of hyperplane arrangements admit Hamiltonian paths?
Consider a simple hyperplane arrangement $H_1,\cdots,H_n$ in the Euclidean space $\mathbb{R}^d$. By "simple" we mean any $k$ hyperplanes in $\{H_1,\cdots,H_n\}$ intersect in codimension $k$. ...
0
votes
2
answers
73
views
Isometric path cover number of the 2 dimensional grid graph
I am looking for a proof of the fact that at least $2n/3$ isometric paths (i.e. shortest paths between the end points) are required to cover the vertices of the $n\times n$ grid graph (i.e. Cartesian ...
5
votes
0
answers
116
views
If chromatic polynomials for two graphs agree, can I always find an edge such that the two deletion-contraction minors have same chromatic polynomial?
Suppose I have non-isomorphic graphs $G$ and $H$ (which have at least one edge), but such that their chromatic polynomials are the same. Can I then always find an edge $e$ in $G$ and $f$ in $H$ such ...
6
votes
1
answer
143
views
Approximating distance on a finite graph with Hamming distance
For this question, all graphs are understood to be finite, simple, and undirected. The distance metric on a graph $G$ means the length of the shortest path between the given vertices, i.e., for $v_1, ...
1
vote
0
answers
33
views
Can we say a partial order set is 2-dimensional if its comparability graph does not contain an asteroidal triple?
I think it is true that if the comparability graph of a poset contains an asteroidal triple then it is at-least 3 dimensional. I want to know if the converse is true, i.e. if there exists no ...
3
votes
0
answers
103
views
Finite approximability of graphs with finitely many automorphisms
In this question, all graphs are understood to be simple and undirected, and have countably many vertices and edges, but not necessarily finite.
Let $G = (V, E)$ be a graph. It is clear that any ...
4
votes
0
answers
214
views
Optimal colorings
If $G=(V,E)$ is a graph, we call the smallest cardinal $\kappa$ such that there is a coloring map $c:V\to \kappa$ as the chromatic number of $G$ and denote it by $\chi(G)$.
For any coloring $c:V(G) \...
0
votes
0
answers
23
views
Algorithm of finding and counting cycles of varying lengths in dynamic or evolving graphs? [closed]
In this paper Alon, N., Yuster, R. & Zwick, U. Finding and counting given length cycles. Algorithmica 17, 209–223 (1997)., the authors present various methods for efficiently locating and tallying ...
1
vote
3
answers
160
views
Graph on $\mathbb{N}$ where almost every vertex is shy
The following question is loosely based on the friendship paradox.
Let $G=(V,E)$ be a simple, undirected graph. For $v\in V$, we let the neighborhood of $v$ be $N(v) = \big\{w\in V:\{v,w\}\in E\big\}$ ...
1
vote
1
answer
30
views
Homomorphisms relationship with Graph Degeneracy
Let $H, G$ be finite undirected graphs. We say that $H$ is $r$-degenerate if there exists an ordering of the vertices of $H$ such that the back degree of every vertex is at most $r$. This is ...
0
votes
0
answers
64
views
What is the complexity of computing isomorphism of two non-regular graphs?
Regular graphs are the graphs in which the degree of each vertex is the same. Much research has gone into investigating isomorphism of regular graphs, and we know that computing isomorphism for ...
5
votes
1
answer
188
views
Chromatic number of the infinite Erdős–Hajnal shift-graph
For any set $X$, let $[X]^2= \big\{\{x,y\}: x\neq y \in X\big\}$. Let $\kappa$ be an infinite cardinal. Let $G_\kappa = ([\kappa]^2, E_\kappa)$ where $E_\kappa = \big\{\{a,b\}\in \big[[\kappa]^2\big]^...
4
votes
1
answer
201
views
Double cover the edges of a complete graph by smaller complete graphs
Suppose we have a complete graph $K_n$ on $n$ vertices. Are there any results on the ways to cover $K_n$ with $k$ copies of $K_m$, for $m<n$, such that each edge of $K_n$ is contained in exactly ...
3
votes
1
answer
109
views
Chromatic number of triangle-free graph $[[n]]^2$ with edges of form $a<b, b<c$
I am reading (and enjoying!) Bela Bollobas' book "Modern Graph Theory", and one of the exercises shows how to construct triangle-free graphs with large chromatic number:
For any non-negative ...
1
vote
2
answers
371
views
What is the proper name for this "tersest path" problem in Infinite Craft?
The web game Infinite Craft gives you a starting set of elements $V_0\subset V$ and a mapping $E$ of type $V\times V\rightarrow V$. In fact, $F$ is commutative: $E(v_a,v_b) = E(v_b,v_a)$. So another ...
3
votes
1
answer
184
views
Some questions about induced subgraphs of the directed hypercube graph
Let $Q^n$ be the hypercube graph in $n$ dimensions. Hao Huang famously showed that any induced subgraph on more than $2^{n-1}$ must have maximum degree $ \geq \sqrt{n}$. It is also known that this ...
3
votes
2
answers
105
views
Let $G$ be a graph of genus $g$. Is the number of (non necessarily disjoint) 5-clique subgraphs at most $f(g)$ for some function $f$?
For a graph of genus $g$, it holds that it cannot have too many disjoint 5-cliques, as each clique requires a new handle. It feels that given a graph of genus $g$, it cannot have an unbounded number ...
1
vote
1
answer
103
views
A reliable reference for the statement every $k$-tree is uniquely $(k + 1)$-colorable
I see that every $k$-tree is uniquely $(k + 1)$-colorable in Uniquely_colorable_graph.
Wikipedia does not cite any references, even though I know that its proof is not difficult by using mathematical ...
0
votes
0
answers
55
views
Names for product-like algebras involving a "duo of directed pseudoforests"
I am looking for the names (and/or for any information regarding) two algebras, one "free" and one "restricted" by an equivalence class.
In both cases, there is an (infix) binary ...
0
votes
1
answer
100
views
Finding automorphism groups of regular graphs [closed]
Can some body help me with some source code for finding automorphism groups of regular maps?. For example: the type of graph is denoted as $\{p, q\}$, which means that they are tessellations of the ...
1
vote
0
answers
51
views
Clique complex of expander graphs simply connected?
Given an expander graph family (an injective sequence of graphs with uniformly bounded vertex degree and a Cheeger constant/Laplacian spectral gap uniformly bounded away from zero).
Can the ...
10
votes
1
answer
259
views
Do triple-linked graphs exist?
Lets say that a finite simple graph $G$ is (intrinsically) fully triple-linked if for each embedding of $G$ into $\Bbb R^3$ we can find three disjoint cycles $C_1,C_2,C_3\subset G$ whose embeddings ...
0
votes
0
answers
23
views
Building hypercubes from the bottom up
let $H^k$ denote a $k$-dimensional hypercube in a complete symmetric graph $G(V,E)$ without self-loops and parallel edges; let $|V|=2^n$ be the number of vertices.
setting
$\mathbb{H}^0 := V$, i.e. ...
0
votes
1
answer
56
views
Regular maps on hyperbolic plane for large number of vertices
I want to generate large regular maps of a tiling on hyperbolic space. How I can start doing that?
10
votes
1
answer
854
views
Could someone explain the proof of this formula clearly? I got the wrong values for spanning trees with this formula and with Cayley's formula
The passage quoted below is from "The number of spanning trees of a graph" by Jianxi Li, Wai Chee Shiu, and An Chang, Applied Mathematics Letters 23.3 (2010): 286-290, DOI:10.1016/j.aml.2009....
0
votes
0
answers
104
views
Using matrix tree theorem on enlarged graphs
The matrix tree theorem for weighted graphs
Seeing this question left me wondering, is it possible to modify the matrix so one can compute the following sum:
$$
P'(G) = \sum_{T\subseteq G}{m'(T)}
$$
...
2
votes
1
answer
135
views
Invertibility of message passing with invertible parametrization
Consider the message passing framework defined by, $$f(\boldsymbol{x}_i)= \boldsymbol{x}_i + \sum_{j \neq i} (\boldsymbol{x}_i -\boldsymbol{x}_j) g(\|\boldsymbol{x}_i -\boldsymbol{x}_j\|^2),$$ for $i=...
6
votes
0
answers
87
views
The uniform odd and even subgraph of $\mathbb{Z}^2$
Given a (first finite and later infinite) graph $G =(V,E)$ the uniform even graph is the uniform probability measure on the set of spanning even subgraphs. That is subgraphs (V, E') with $E' \subset E$...
2
votes
1
answer
95
views
Exhaustive list of small graphs for which $\frac{\alpha(G)\omega(G)}{n}$ is small?
I am looking for a list of small graphs (say on less than 10 vertices) for which the parameter $p(G) = \frac{\alpha(G) \omega(G)}{n}$ is small. Here $\alpha(G)$ and $\omega(G)$ is the size of the ...
2
votes
1
answer
128
views
Bipartite matching with a pairwise constraint
A long time ago I remember seeing a very clever construction for the following problem, but I can't find a reference for it anywhere: suppose I have a bipartite graph $G=(U\cup V, E)$, and the ...
5
votes
0
answers
129
views
Given a collection of vectors $x_1,\ldots,x_k$, which inner products $\langle x_i,x_j\rangle$ are needed to uniquely determine all inner products
Given a collection of vectors $x_1,\ldots,x_k$, which inner products $\langle x_i,x_j\rangle$ need to be known to uniquely determine all inner products? I'll begin with the specific case I am ...
4
votes
1
answer
154
views
Probability problem in Sheehan's conjecture
As my first math project, I have been working on Sheehan's Conjecture
and am stuck for weeks. I wonder if I am at a dead end.
Sheehan's Conjecture states that every Hamiltonian 4-regular simple
graph ...
0
votes
0
answers
69
views
Graphs where any cycles are adjacent
Graphs with minimum degree three that any two cycles have common vertex, have been characterized by Lovász. I see this result from the Plumer article (On the cyclic connectivity of planar graphs (...
5
votes
1
answer
139
views
Given a 3-connected graph $G$, is there an edge $e$ so that both $G-e$ and $G/e$ are still 3-connected?
Let $G$ be a 3-connected (simple) graph other than $K_4$. In Diestel's "Graph Theory" Section 3.2 we find
Lemma 3.2.2. There is an edge $e$ so that $G\mathbin{\dot-}e$ is still 3-connected (...
2
votes
1
answer
215
views
Name for generalization of trees to digraphs
One definition of tree in graph theory could be as follows:
A tree is a(n undirected) graph for which there is a unique (undirected) path between any pair of vertices.
This suggest a possible ...
15
votes
1
answer
866
views
Scrambling a “Connections” grid
Given a 4-by-4 array of distinct words, is it possible to scramble the array in four different ways in such a fashion that each possible word-pair appears adjacently in one of the five arrays (the ...