All Questions
Tagged with reference-request graph-theory
453 questions
11
votes
1
answer
395
views
Dense triangle-free graphs and their independent sets
Recall that a graph is triangle-free if it does not contain a copy of $K_3$. Also, for a graph $G$, $\alpha(G)$ shall denote its independence number. Lastly, we will write $o(1)$ to denote quantities ...
- 3,499
15
votes
1
answer
746
views
Page-turning number of a graph
Motivation. As I was travelling in the UK, I used a physical copy of the "A-Z Road Atlas BRITAIN" for getting around. I was impressed that whenever I wanted to go from the map segment shown ...
- 48.9k
10
votes
3
answers
931
views
"Gluing and copy" graphs
Consider the minimal class of (simple, undirected) connected graphs (strictly speaking, isomorphism classes of connected graphs) which contains a single vertex $K_1$, and is closed under following ...
- 109k
1
vote
0
answers
85
views
Graph energy and spectral radius
Suppose $G$ is a simple graph of order $n$ with eigenvalues $\lambda_1\geq \cdots\geq \lambda_n$. I've encountered the quantity $L=\big\vert |\lambda_1|-|\lambda_2|-\cdots-|\lambda_n|\big\vert$. Note ...
- 171
4
votes
0
answers
157
views
Independent sets with few neighbours
[Posted this first at math stackexchange, but it probably fits better here.]
I am looking for references about the following problem.
Given a (connected) bipartite graph $G$, find an independent set $...
- 338
1
vote
0
answers
384
views
Counting number of spanning trees of the complete bipartite with given vertex-degrees
For given $n_1,n_2 \in \mathbb{N}$ let $K_{n_1,n_2}$ be the complete bipartite graph. I have seen a few sources proving that the number of spanning trees $t(K_{n_1,n_2})$ is given by $n_1^{n_2-1} n_2^{...
- 1,295
2
votes
1
answer
254
views
Is there a formula for the number of trees with this extra condition?
A tree $G$ on $n$ vertices $V=\{v_1,...,v_n\}$ is a connected undirected graph which is acyclic. For each tree $G$ one can split the set of vertices $V$ into two disjoint subsets $U,W \subset V$ such ...
- 1,295
1
vote
0
answers
52
views
Standard test for the recognition of toroidal graphs
Is there a standard test for the recognition of toroidal graphs? I have been using the Boyer–Myrvold planarity algorithm, which has a MATLAB and C++ implementation.
- 11
3
votes
0
answers
152
views
Free $2$-category on a $2$-quiver
The construction of the free category on a quiver is standard in category theory.
Is there some $2$-dimensional analog of a quiver such that each $2$-quiver freely gives rise to a $2$-category? How ...
- 10.1k
0
votes
0
answers
120
views
Does an extension of the B.E.S.T. theorem for multiple Eulerian circuits exist?
Given a directed multigraph $G=(V,E)$ (multiple edges and loops are permitted) the number of distinct Eulerian circuits for $G$ can be calculated with the B.E.S.T. theorem. Does a similar theory for ...
- 1,295
1
vote
2
answers
418
views
Graphs constructed from sums of perfect matchings
Consider the following natural procedure for constructing graphs from perfect matchings in graphs with even number of vertices.
Let $V$ be the set of vertices of cardinality $|V|=2n$ and let $\mathcal{...
- 965
3
votes
1
answer
600
views
Is there a permutation invariant for graphs?
Let $V = (v_1,...,v_n)$ be a set of vertices for a directed graph. We denote an edge between the two vertices $v_i$ and $v_j$ by $(i,j)$. The edge set $E$ for a graph $(V,E)$ is then a set of tuples $...
- 1,295
3
votes
1
answer
200
views
Maximum number of edges in a "coprime graph"
Let's define a coprime graph as a simple graph (undirected graph without any self-loops or multiple-edges) in which for all edges $(𝑢, 𝑣)$, the property $\gcd(\mathrm{degree}_u, \mathrm{degree}_v) = ...
1
vote
0
answers
50
views
Reference for a lemma on acyclic subgraph
Lemma. Let $D$ be a digraph. Then there exists an acyclic subdigraph $D'$ of $D$ such that the total degree (i.e. out-degree plus in-degree) of $v$ in $D'$ is at least the out-degree of $v$ in $D$ for ...
- 121
2
votes
0
answers
54
views
Do there (or might there) exist computable invariants for Aut(G)-invariant subgraphs of a graph G?
I am interested in algorithms for computing all subgraphs (not necessarily induced) of a graph $G$ up to $Aut(G)$ isomorphism. I had the idea of partitioning the edges of the graph like so
$$\{F|E(G)\...
- 161
2
votes
0
answers
106
views
Decomposing a planar graph
Thomassen proved that the vertex set of every planar graph can be decomposed into two sets inducing a 1-degenerate graph and a 2-degenerate graph, respectively (C. Thomassen, Decomposing a planar ...
- 3,153
4
votes
1
answer
553
views
Product of vertex degrees of an edge in a planar graph
Let $G$ be a planar graph, which we may assume to be a triangulation, with vertex set $V$ and edge set $E$. Suppose the minimum vertex degree is at least 3, and suppose any two distinct edges share at ...
- 565
7
votes
2
answers
595
views
A 2-page paper on a lower bound of Ramsey number
I'm looking for a 2-page paper on a lower bound of Ramsey number $R(a,b)$ for some constants $a$ and $b$. The paper was published in 80s or 90s. I googled it for a few days, but I cannot find the ...
- 71
2
votes
2
answers
183
views
Name of an inductively defined sequence of graphs
Let $G_k$ be the graph obtained by applying the following procedure k-times:
Start with a graph with single vertex $v$ (Call this graph $H$)
Add a vertex $u$ such that $u$ is not adjacent to any ...
- 1,269
15
votes
1
answer
518
views
Reference request: Moore graphs
It is clear that the term Moore graph was coined by Hoffman and Singleton in their paper On Moore graphs with diameters $2$ and $3$, where they write
E. F. Moore has posed the problem of describing ...
- 2,339
4
votes
0
answers
59
views
Graph-class defined by matrix-like vertex-operations
Let $m$ be a positive integer. We define a (directed) graph on $m(m-1)$ vertices
$$V = \bigl\{(i,j) \mid i \ne j,\, i,j\in\{1,\dots,m\}\bigr\}$$
and edges as follows:
$(i,j) \in V$ is adjacent (...
- 577
5
votes
0
answers
231
views
Schröder and graphical logic?
I was actually surprised by a comment by John Baez over at the n-Category Cafe about his surprise that Ernst Schröder, a mathematician of whom he had known through Schröder's work on mathematical ...
- 10.5k
6
votes
1
answer
746
views
Relationship between spectral gaps of adjacency and Laplacian matrices of graphs
Let $G$ be an undirected simple graph on $n$ vertices, with self-loops allowed, and with arbitrary positive edge weights $w_{u,v}$ (which is $0$ if there is no edge between $u$ and $v$).
Let $A$ be ...
- 150
3
votes
1
answer
325
views
Is anything written about winning the "Dollar Game" in the minimal number of moves?
I run some Master's projects on Chip-Firing games, using the Holly Krieger's Numberphile video on the topic as an initial motivation, and going on to prove the main theorem stated there (that you can ...
- 2,372
22
votes
2
answers
900
views
Is every 1-million-connected graph rigid in 3D?
It is an old result that every $6$-connected graph is rigid in $\mathbb{R}^2$:
Lovász, László, and Yechiam Yemini. "On generic rigidity in the plane." SIAM Journal on Algebraic Discrete ...
- 151k
1
vote
0
answers
72
views
Another betweenness centrality measure: neighbourhood centrality
Among the many centrality measures that I have heard of, I miss the following (but maybe I'm just blind).
Consider a graph $G$ with $k$ connected components $G_i$ of size $|G_i|$. The number of node ...
- 9,720
4
votes
2
answers
2k
views
The number of monochromatic triangles
It is well known that the minimum number of monochromatic triangles in a red/blue coloring of the edges of the complete graph $K_n$ is given by Goodman's formula
$$M(n)=\binom n3-\left\lfloor\frac n2\...
- 13.4k
1
vote
0
answers
340
views
Random walk on non-abelian free group
Let $F_2$ be the free non-abelian group with generators $a, b\in F_2$.
Has the "random walk" where we start with the identity and then multiply it by $a$ or $b$ or $a^{-1}$ or $b^{-1}$ ...
- 11
1
vote
0
answers
152
views
Is this graph theory paper in German translated into English?
I recently read such a paper and want to understand the proof idea of this article. However since it is in German and I have not studied German before, I'd like to ask whether this paper has an ...
- 1,851
7
votes
2
answers
637
views
Line graphs called "graph derivatives": any intuition?
Short version: in several papers, line graphs (and closely related graphs) are called graph derivatives or derived graphs; is there any intuition for such terminologies, in connection with the ...
- 1,444
34
votes
1
answer
789
views
Which graphs on $n$ vertices have the largest determinant?
This is a question that seems like it should have been studied before, but for some reason I cannot find much at all about it, and so I am asking for any pointers / references etc.
The determinant of ...
- 12.7k
20
votes
6
answers
4k
views
Graph theory from a category theory perspective
Are there any textbooks on graph theory written for a category theorist?
It would probably have to be on directed graph theory, but if there's some trick we can use to talk about undirected graphs as ...
1
vote
0
answers
35
views
Term or reference for a set of integer edge weights to guarantee distinct weighted degrees
I am looking for a term or reference describing sets $S$ of $\binom{n}{2}$ non-negative integers such that, for every bijection $w: E(K_n)\to S$ and every pair of distinct vertices $u$ and $v$ in $V(...
- 11
7
votes
0
answers
97
views
What is known about chromatic polynomial of hypergraph at $-1$
Let $H$ be a hypergraph and let $P_H$ denote its chromatic polynomial. I am interested in the best results interpreting $P_H(-1)$. I am interested both in the general case (which I think is hard) as ...
- 7,875
2
votes
1
answer
127
views
The density of a tripartite 1-planar graph
1-planar graphs are those can be drawn in the plane so that there is at most one crossing per edge. We know that the maximum number of edges of an $n$-vertex 1-planar graph is at most $4n-8$, and the ...
- 1,190
2
votes
1
answer
106
views
Are zonotopes determined by their edge-graph?
General polytopes are not determined by their edge-graph (up to combinatorial equivalence). But I came accross the statement that zonotopes are determined in this way.
Question: Is this true? And ...
- 13.6k
2
votes
0
answers
905
views
Confusing notation for sets of unordered vs ordered pairs
Given two finite sets $X$ and $Y$, one may consider the ordered pairs $(x,y)$ with $x\in X$ and $y \in Y$. Then, $(x,y) \not= (y,x)$, and $(x,x)$ exists if $x\in X$ and $x\in Y$.
One may also consider ...
- 1,444
1
vote
0
answers
102
views
What is the real name for the initial object in the category of "monoid-valued measures of intervals" on transitive relations?
(I'm not asking for a true/false answer; I have a true algebraic fact and I'm looking for a reference in the literature. By the way, there is a version of this theorem that replaces monoid with $R$-...
3
votes
2
answers
2k
views
Proving that every strongly connected tournament T on at least 4 vertices contains distinct vertices u, v such that T-u and T-v are strongly connected
I have a two part question:
Is there a simple proof that every strongly connected tournament $T$ on $n\geq 4$ vertices contains distinct $u,v\in V(T)$ such that $T-u$ and $T-v$ are strongly connected?...
- 1,701
2
votes
0
answers
129
views
Decomposing a metric tree as a union of rooted (or "centered") trees
Suppose $G$ is a finite metric tree whose set of leaves is $A=\{v_1, \ldots, v_n\}$. Consider the function $G\to \mathbb R_+$ that assigns to a point $x$ the distance from $x$ to $A$, denoted $d(x, A)$...
- 10.9k
13
votes
0
answers
237
views
A Dynkin type classification result in linear algebra
Let $G$ be a finite directed acyclic graph. The Cartan matrix $C_G=C$ of $G$ is defined as the matrix with rows and colums indexed by the vertices of $G$ and $c_{i,j}$ counts the number of paths from $...
- 26.5k
8
votes
0
answers
181
views
Self-avoiding walks on strips
A strip is a locally finite graph which admits a quasi-transitive (i.e. finitley many orbits on vertices) action of $\mathbb Z$. A self avoiding walk is a walk which visits no vertex more than once.
...
- 2,671
7
votes
2
answers
186
views
Graph embedding that locally minimizes total edge lengths
I consider a graph $G$ (possibly infinite, but locally finite) embedded in the Euclidean plane $\mathbb{E}^2 \cup \{\infty\}$ such that each local perturbation of the embedding "increases the ...
- 2,581
2
votes
1
answer
181
views
Generators of sandpile groups of wheel graphs
In the paper "On the Sandpile Group of a Graph" by Cori and Rossin one can find a result related to the structure of the sandpile group of $W_n$. Is there a way to provide a set of ...
- 298
3
votes
2
answers
406
views
What is the definition of brick product of graphs?
Can anyone help me with the exact definition of brick product of graphs, say path, cycle.
I am not able to find a paper with a clear definition on the internet. Can anyone give me a URL to such a ...
- 101
5
votes
1
answer
788
views
Deleting triangles in a graph
I'm sure it is well-known how many edges you must delete in a (highly linked) graph to destroy all cycles. Is it also known how many edges you must delete to destroy only all triangles? And even, how ...
- 4,829
0
votes
1
answer
77
views
Fourth moment of a random-variable with block-tridiagonal structure
Let x be a random variable in $\mathbb{R}^d$, $J$ a block tridiagonal $d\times d$ matrix, and probability of $x$ is defined as follows
$$p(x)\propto \exp(-x'Jx)$$
For a fixed $d\times d$ matrix $v$ ...
- 2,252
0
votes
0
answers
140
views
Graph theory: Closed neighourhoods and generalized clustering coefficients
The neighbourhood of node $v$ in graph $G$ is the subgraph of $G$ induced by all vertices adjacent to $v$.
The number of edges between neighbours divided by the number of pairs of neighbours is ...
- 9,720
0
votes
0
answers
142
views
Counting special paths on a certain rectangle integer grid (binary matrix)
Crossposting from MSE after getting no answers. The bounty on the MSE question is still open, but not for long. Be advised that the comments of the MSE question regard an obsolete version, and that ...
- 149
2
votes
0
answers
86
views
Optimal paths in set-weighted graphs
Let $G = (V,E)$ be an $n$-vertex graph, let $R$ be a finite set (to be specific, let us assume that $R = [n]$), and let $W : V \rightarrow 2^R$. Let us call the pair $(G, W)$ a set-weighted graph.
Now ...
- 655