All Questions
Tagged with reference-request graph-theory
453 questions
8
votes
4
answers
1k
views
Counting with trees
Let $\mathcal{U}_n$ denote the set of unrooted unlabelled trees with $n$ edges. For $T\in\mathcal{U}_n$, let $1^{u_1}2^{u_2}\cdots n^{u_n}$ be its degree distribution, that is, $u_i=\#$ of vertices ...
- 43.2k
3
votes
0
answers
61
views
Is this bipartite equivalent of 1-walk-regular graphs known?
A graph $G$ is 1-walk-regular if
for each vertex $v$ the number of closed walks of length $\ell$ starting (and ending) at $v$ depends only on $\ell$ but not on $v$.
for each edge $vw$ the number of ...
- 13.6k
0
votes
0
answers
85
views
Uniqueness of compatible cycle decomposition for Eulerian trail
Fleischner mentions in his article Uniqueness of maximal dominating cycles in 3-regular graphs and of hamiltonian cycles in 4-regular graphs about the uniqueness of compatible cycle decomposition that ...
10
votes
2
answers
598
views
Is there a "simplest" way to embed a graph in 3-space?
I consider embeddings of graphs into 3-space with edges embedded as arbitrary curves. In the simplest (non-trivial) case the graph $G$ is a cycle or union of cycles, in which case the embeddings can ...
- 13.6k
1
vote
1
answer
82
views
Channel Capacity & Dependency Graph
A single-input-single-output communication channel is to be used repetitively. Denote by $X_i \in \mathcal X$ the input at time $i$ and by $Y_i \in \mathcal Y$ the output at time $i$.
Assume the ...
- 115
3
votes
1
answer
108
views
Has this random process been studied on grid graphs?
As an offshoot of a different discussion I got curious about (uniform) random spanning trees on grid graphs (torus graphs in particular, to avoid having to think about edge effects) and what their ...
- 1,951
3
votes
1
answer
140
views
Generalizations of a theorem of Edmonds/Tutte on existence of a perfect matching in a graphs
It is well known that for a bipartite graph $G$ with bi-adjacency matrix $A$, then $\det A \neq 0$ (as a polynomial) iff $G$ has a perfect matching (there is a similar result for general graphs with ...
- 129
1
vote
0
answers
45
views
A new graph product and its properties
We define a sequence of graphs $\{B_0, B_1, \dots B_k \dots \}$ as follows:
Consider a seed graph $B$ with a vertex set $V(B) = \{v_1, v_2, \dots v_n\}$ and an edge set $E(B)$. The sequence is ...
- 363
2
votes
0
answers
126
views
A reference for high girth expander graphs
I'm looking for a reference to the existence of family of constant (or bounded by constant) degree graphs which are both high-girth (meaning the ratio girth/diameter is uniformly bounded from below by ...
- 401
0
votes
0
answers
57
views
Reference for packing property and König property
Can someone please suggest reference material to study about the packing property and König property of ideals and some examples?
- 21
3
votes
1
answer
271
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$ ...
- 33
0
votes
2
answers
96
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 ...
- 1,305
5
votes
0
answers
141
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 ...
- 15.8k
4
votes
1
answer
222
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 ...
- 43
1
vote
1
answer
107
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 ...
- 1,851
0
votes
0
answers
56
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 ...
2
votes
1
answer
152
views
First known proof of the $2 \cdot n-2$ Theorem for the planar generalization of the Nine dots problem
Reading the Wikipedia page about the well-know Nine dots puzzle, I have just seen that the planar generalization of this problem would have been proven in 1956 (see Wikipedia: Nine dots puzzle), while ...
- 1,451
7
votes
1
answer
300
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 ...
- 1,851
1
vote
1
answer
177
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-...
- 243
0
votes
2
answers
118
views
Why is a plane graph Delaunay realizable if stellating a face makes the graph inscribable?
I have come across the following lemma in several papers (for instance see lemma 2.2 in this) (and some authors state this the proof immediately follows from basic properties of the stereographic ...
- 129
3
votes
1
answer
158
views
Sharp upper bound of the number of edges for graphs of thickness two
A graph $G=(V,E)$ has thickness $2$ if $E$ can be written as a disjoint union $E=E_1\cup E_2$ so that $G_1:=(V,E_1),G_2:=(V,E_2)$ are planar graphs. For instance, $K_5$ has thickness $2$. It is known ...
- 1,075
1
vote
0
answers
64
views
Colorability classes of graphs
Let $G=(V,E)$ be a simple, undirected graph, finite or infinite, with $V \neq \emptyset$. We consider the chromatic number $\chi(G)$ as a cardinal. We say that colorings $c:V\to \chi(G)$ are proper ...
- 48.9k
1
vote
2
answers
130
views
Constants for diagonal hypergraph Ramsey Theorem
For integers $n,s$, we write $K_n^{(s)}$ to denote the complete $s$-uniform hypergraph on $n$ vertices.
Given integers $k,s,r$, let $R(K_k^{(s)};r)$ denote the smallest $N$ such that, for every $r$-...
- 3,499
5
votes
0
answers
121
views
The Smith decomposition of the graph Laplacian and Locality
Let $X$ be a graph. Let $V(X)$ and $E(X)$ be the sets of vertices and edges of the graph respectively. If $f:V(X) \rightarrow G$ where $G$ is an abelian group, then one can define a graph Laplacian as ...
- 51
2
votes
1
answer
126
views
"Balanced" separator which is independent set
I am looking for existence results on separators of $r$-regular graphs $G=(V,E)$, which have the property that
$S\subset V$ is a separator
for all $v,w\in S$ the edge $\langle v,w\rangle\not\in E$ (i....
- 91
4
votes
2
answers
237
views
Reference request for differential graph theory
Disclaimer: This question was initially asked yesterday in Mathematics Stack Exchange but left unanswered there.
I am interested in learning about differential graph theory or differential operators ...
2
votes
1
answer
248
views
Connected components in random regular graphs
Suppose we take a random regular graph $G_{2n, r}$, where $n$ is large. Let us also assume that $r$ is fixed, (not dependent on $n$). Let's say that half of the vertices of the graph are colored black ...
- 1,407
4
votes
0
answers
185
views
Olympiad problem relevant to $(a,b)$-feasible pair
Recently, a mathematical olympiad problem is proposed as follows:
Let $G$ be a graph with $|V| = 100$ and $\delta(G) \geqslant 10$. Prove that there is an integer $0 \leqslant k \leqslant 5$, such ...
6
votes
0
answers
373
views
Circle numbers on edges of a graph
Let $k$ vertices in a graph be given. Some pairs of vertices are connected by an edge, each edge is labeled either $\{1,2\}$, $\{1,3\}$, or $\{2,3\}$. We can circle some of the numbers on the edges. ...
- 277
0
votes
0
answers
102
views
Merging two composable walks in a graph
Let $G$ be a graph (i.e., an undirected graph in which we allow for loops and parallel edges). Denote by $V$ the vertex set, by $E$ the edge set, and by $\psi$ the incidence function of $G$, and let $\...
- 10.5k
2
votes
1
answer
104
views
Characterization of graphs without leaves
Let $G(n,l)$ denote the set of connected graphs with $n$ vertices and $l$ edges and let $G_0(n,l)$ denote the elements of $G(n,l)$ without leaves. It is easily seen that $G_0(n,n-1)$ is empty, since $...
- 1,295
2
votes
0
answers
65
views
Structure Theory for Tree Decompositions
I that $G=(V,E,W)$ is a weighted graph with positive edge weights and a finite set of vertices $K$. Let $0\le k,M\le K$ be a fixed integer.
Is is known when $G$ admits the following type of ...
- 21
1
vote
0
answers
48
views
Metrics on paths in digraphs
I'm looking for metrics (or even just symmetric dissimilarities) on finite paths in finite digraphs but not finding anything in the literature. Can anyone point me to references?
I've looked in Deza ...
- 15.4k
3
votes
2
answers
478
views
Random spanning trees probability problem
We are given a simple connected graph $G(V,E)$ with vertex and edge set $V$ and $E$ respectively. For any vertex $v\in V$, let $D_T(v)$ the degree of $v$ in a uniformly generated random spanning tree $...
- 1,677
1
vote
2
answers
104
views
The number of maximal cliques of the intersection graphs
Are there some results about the upper bound of the number of maximal cliques (NMC) of some class of intersection graphs?
I want to know whether some classic classes of intersection graphs have ...
- 1,503
0
votes
2
answers
157
views
Dense vertex-symmetric graphs with high girth
I am looking for existing constructions of vertex-symmetric graphs on $n$ nodes that have a girth at least $g$ and are dense, i.e., have at least $n^{1 + \epsilon}$ edges, where $\epsilon>0$ may ...
0
votes
0
answers
84
views
Bounds for smallest non-trivial designs
Given $s>t\ge 2$, let $N(s,t)$ be the smallest integer $n>s$ such that there exists an “$(n;s;t;1)$-design” (i.e., a collection of $s$-subsets $e_1,\dots,e_m$ of $[n]:=\{1,\dots,n\}$, such that ...
- 3,499
5
votes
1
answer
107
views
Maximal graphs with a property that is invariant w.r.t. vertex removal
Let $P$ be a property of graphs such that if a graph $G$ has $P$, then any graph obtained from $G$ by removal of a vertex also has $P$.
Let $g(n)$ be the maximum size of a graph of order $n$ having $P$...
- 34.3k
2
votes
1
answer
157
views
Bound for a sequence of vertices in a graph
I have come across the following problem. Let $d\in\mathbb{N}$. Let $G$ be any $k$-regular connected directed graph with $n$ vertices, no parallel edges and no 2-cycles. For a vertex $v\in G$, let $...
- 167
1
vote
1
answer
438
views
Categories associated to digraphs
Let's take a directed graph, or a digraph, $G=(V,E)$ given by a finite set of vertices $V$ and a finite set of edges $E$. We can assume that pairs of vertices can have parallel edges between them and ...
0
votes
0
answers
55
views
Comparing spectral radius of two graphs using the entry of Perron vector
Suppose we have a graph $G$.
Let $A$ be the adjacency matrix of $G$ and $x$ be the corresponding Perron vector.
Let $x = (x_1,x_2,\cdots,x_n)^t$, where $x_i$ corresponds to the vertex $i \in V(G)$.
We ...
- 199
8
votes
0
answers
245
views
Did these graphs pop up somewhere?
Please let me know if the following graphs popped up in some problems.
Each of these graphs is described by 5 integers $n_1\geqslant k_1$, $n_2\geqslant k_2$, $l\geqslant 0$.
We take two complete ...
- 45k
2
votes
1
answer
173
views
Matching polynomial, but $K_2$ is replaced by $K_3$. Have these been studied?
Given a simple graph $G=(V,E)$, we can consider matchings, $M\subseteq E$,
where $M$ is a matching iff no vertex is shared between different edges.
The number of edges in $M$ is denoted $|M|$.
The ...
- 15.8k
1
vote
0
answers
74
views
Keller's cubing conjecture but with arbitrary cubes of side $1$
These days I have been reading about Keller's cube tyling conjecture, which asks if in any covering of $\mathbb{R}^n$ by translates of $[0,1]^n$ with disjoint interiors there are two cubes sharing one ...
- 10.6k
4
votes
0
answers
43
views
On the connection graphs-knots-tensors
You can interpret a featureless graph as product of featureless abstract tensors; the tensors are then automatically totally symmetric as "leg crossing" in the graph interpretation is the ...
- 4,829
4
votes
0
answers
89
views
How to measure the optimality of the induced order by a median order of a tournament on a big subset
Median orders are great tools for dealing with a-priori unknown orientations of edges in tournaments, because they provide us with local properties on oriented edge density.
I've been wondering if ...
- 71
0
votes
0
answers
78
views
Sum of products on a directed acyclic graph
Is there a textbook/paper that I can reference for the following problem? I am looking for a concise proof that I can cite.
Let $G=(V,E)$ be a weighted directed acyclic graph, and consider
$s,t\in V$....
- 101
11
votes
0
answers
537
views
Outline of the unpublished proof of Erdős-Sós conjecture
In this post, it was mentioned that a long time ago, Ajtai, Kolmós, Simonovits, and Szemerédi announced a proof that for sufficiently large $k$, every $k$-vertex tree $T$ is a subgraph of every graph $...
- 3,499
2
votes
0
answers
165
views
Has Mac Lane's article "When can a graph be mapped on a torus?" been published anywhere?
I came across the following abstract of an article: Mac Lane, S., When can a graph be mapped on a torus?, Bull. Amer. Math. Soc. 42(9), 629 (1936). Abstract #341. MR1563375, JFM 62.0694.07.
Q. Does ...
- 1,446
3
votes
0
answers
144
views
Counting homologically non-trivial and trivial cycles in $n \times n$ square lattice torus of a given length $l \geq n$
This should be a fairly standard question but I can't really seem to find a reference.
Consider an $n \times n$ square lattice torus $\mathbb T$. Given a length $l \geq n$, what is the number of ...
- 269