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,139
questions
1
vote
0
answers
56
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$ ...
0
votes
0
answers
33
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
104
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
1
answer
31
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
110
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
111
views
+100
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
28
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
100
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 ...
3
votes
0
answers
204
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
20
views
Algorithm of finding and counting cycles of varying lengths in dynamic or evolving graphs?
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
153
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
28
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
59
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
183
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
197
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
106
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
357
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
168
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
101
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
54
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
99
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
50
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
252
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
49
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
847
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
103
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
85
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
93
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
126
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
128
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
152
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
136
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
213
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
862
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 ...
0
votes
0
answers
55
views
How many rigid 4-regular graphs are there?
I am interested in any formulas for the number of globally rigid 4-regular graphs, or Laman graphs of degree at most 4, on $n$ vertices. The bound can be for graphs with labeled or unlabeled vertices.
2
votes
0
answers
72
views
Bound on the magnitude of the entries of the Laplacian pseudo-inverse
Let $L$ be the laplacian matrix of a connected graph $G$ with real positive weights and $N$ vertices, or that can be assumed to have binary weights for simplicity.My goal is to bound $\Vert L^+\Vert_{\...
0
votes
0
answers
35
views
Number of $5^{-}$-neighbors of high-degree vertices in maximal planar graphs
We call a vertex with a degree no more than $k$ a $k^{-}$-vertex and a $k^{+}$-vertex if it has a degree at least $k$. By the discharging method, the researchers in graph theory obtained a series of ...
0
votes
0
answers
65
views
Interpretation of $|V|\,|E|$ for bipartite graphs
Background: the question is motivated by a result in statistical mechanics. I am working with a generalized exclusion process with a fixed number of particles $k$ on a finite graph $G'=(V,E')$, which ...
1
vote
1
answer
108
views
A bound on the number of partial transversals of a latin square
A Latin Square (LS) of order $n$ is an $n$ on $n$ matrix, each entry contains one of the symbols $1,2,\ldots,n$, and every row and every column contains each symbol exactly once. A (complete) ...
1
vote
0
answers
157
views
Locally "unshortable" paths in graphs
Setup: Consider a connected graph G, with diameter "d".
Informally: Trivially (by definition of diameter), taking any path $P$ any nodes $P(i) , P(i+k)$ for $k>d$ can be connected by a ...
9
votes
4
answers
2k
views
A starting point for research in Graph Theory as a high schooler [closed]
I am a 10th grader and I'm very interested in mathematics. As of now, I'm into math contests and I take great pleasure in solving problems from contests such as the AIME/USAMO/IMO. These only require ...
4
votes
1
answer
98
views
If two vertices induce isomorphic subgraphs when they are removed, are they conjugate?
This feels like a very natural question, but I am struggling to find a reference, proof, or counter-example.
Consider a simple graph $G$, and say two vertices are conjugate if there exists an ...
4
votes
1
answer
130
views
Sizes of triangle-free graphs with independence number $k$
A triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. The independence number $α = α(G)$ of a graph $G$ is the cardinality of a maximum in dependent set of ...
3
votes
0
answers
61
views
Second eigenvalue of primitive matrix
Let $A$ be a primitive $N\times N$-matrix with positive entries, that is there is $n>0$ such that $(A^n)_{i,j}>0$ for all $i,j$. For brevity, assume the entries consist only of $0$ and $1$.
The ...
4
votes
0
answers
126
views
"Neighborhood-Bounded" regular graphs
Lately I have been interested in questions surrounding strongly regular graphs, and came across this question that I have been struggling to make progress on. (For the sake of being explicit, a graph $...
0
votes
0
answers
83
views
Hypergraphs where the edges are subsets of the union of the edges and nodes?
Is there a formulation of hypergraphs such that the hypergraph $H = (V, E)$ consists of a set of nodes $V = \{v_1, v_2, ..., v_n\}$ and a set of edges $E = \{E_1, E_2, ...,E_m\}$, where $E_i \subseteq ...