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
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 ...
Joseph Zambrano's user avatar
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 ...
bc a's user avatar
  • 41
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 ...
L.C. Zhang's user avatar
  • 1,605
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 ...
n1ps's user avatar
  • 1
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 ...
Dominic van der Zypen's user avatar
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$...
Hao S's user avatar
  • 181
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|\...
bc a's user avatar
  • 41
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 ...
Hao S's user avatar
  • 181
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 ...
Will's user avatar
  • 105
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 ...
Kuzja's user avatar
  • 101
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 ...
whiterock's user avatar
  • 111
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 ...
Lasting Howling's user avatar
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$ ...
Shean's user avatar
  • 21
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 ...
Sowbarnika R's user avatar
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$. ...
YHBKJ's user avatar
  • 3,127
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 ...
Pritam Majumder's user avatar
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 ...
Per Alexandersson's user avatar
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, ...
David Gao's user avatar
  • 1,262
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 ...
Siddhu Neehal's user avatar
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 ...
David Gao's user avatar
  • 1,262
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) \...
Dominic van der Zypen's user avatar
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 ...
138 Aspen's user avatar
  • 133
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\}$ ...
Dominic van der Zypen's user avatar
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 ...
Sean Longbrake's user avatar
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 ...
Eauriel's user avatar
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]^...
Dominic van der Zypen's user avatar
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 ...
Wallace Rin's user avatar
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 ...
Dominic van der Zypen's user avatar
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 ...
Quuxplusone's user avatar
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 ...
Agile_Eagle's user avatar
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 ...
master bob's user avatar
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 ...
L.C. Zhang's user avatar
  • 1,605
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 ...
user1661473's user avatar
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 ...
Zahid Malik's user avatar
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 ...
Florentin Münch's user avatar
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 ...
M. Winter's user avatar
  • 12.5k
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. ...
Manfred Weis's user avatar
  • 12.6k
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?
Zahid Malik's user avatar
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....
Noxious Reptile's user avatar
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)} $$ ...
juan manuel rodriguez's user avatar
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=...
PonderingPolynomial's user avatar
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$...
Frederik Ravn Klausen's user avatar
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 ...
Agile_Eagle's user avatar
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 ...
Tom Solberg's user avatar
  • 3,929
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 ...
RandomTensor's user avatar
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 ...
Daniel Liu's user avatar
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 (...
L.C. Zhang's user avatar
  • 1,605
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 (...
M. Winter's user avatar
  • 12.5k
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 ...
Manfred Weis's user avatar
  • 12.6k
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 ...
James Propp's user avatar
  • 19.4k

1
2 3 4 5
103