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.
1,486
questions with no upvoted or accepted answers
10
votes
0
answers
164
views
Largest number of simple paths between two vertices
Let $G$ be a simple undirected graph, $f(v, u)$ be the number of simple paths between $u$ and $v$ in $G$, $f(G) = \max f(v, u)$ over all pairs of vertices $v, u \in G$.
A recent IOI problem utilized ...
10
votes
0
answers
431
views
When does a graph have a minimally strong orientation?
Given an asymmetric relation $A\subseteq V^2$ a digraph $D=(V,A)$ is minimally strong iff $D$ is strongly connected and for all arcs $\alpha\in A$ the digraph $D−\alpha=(V,A\setminus\{\alpha\})$ is ...
10
votes
0
answers
715
views
Has this notion of vertex-coloring of graphs been studied?
In a study of a quantum physics problem, I came about an apparently very natural type of vertex colorings of a graph. The colors of the vertex $v_i$ is inherited from perfect matchings $PM$ of an edge-...
10
votes
0
answers
254
views
Fixed point property for simple undirected graphs
We say that a simple, undirected graph $G=(V,E)$ has the fixed point property (FPP) if for every graph homomorphism $f:G\to G$ there is a vertex $v\in V$ such that $f(v) = v$.
If $G$ has the FPP, ...
10
votes
0
answers
655
views
Fractional Matching version of Hall's Marriage theorem
Let $G=(S,T,E)$ be a bipartite graph, $|S|=|T|$. Then the following are equivalent:
1) there exist a perfect matching in $G$;
2) there exist non-negative weights on edges such that the sum of ...
10
votes
0
answers
714
views
Torus Graph Dynamics
Consider the torus graph, or the toroidal grid, which looks like
(The graph's vertices are the bold dots).
I will discuss only square torus graphs, where there is an equal number of vertices in a "...
10
votes
0
answers
216
views
Cospectral mate of rhombic dodecahedron
I am wondering if the following pair of cospectral graphs was previously known.
The rhombic dodecahedron graph looks like this (graph6 string: 'M?????rrAiTOd_YO?'):
As far as I know, it was previously ...
10
votes
0
answers
302
views
Among regular graphs, do cliques have the highest infection rate?
Consider a graph $G$ with a particular node $i$ labeled as “infected”. Other nodes start uninfected, and will become infected over time according to the following process: To each edge of the graph, ...
10
votes
0
answers
217
views
Asymptotics of subgraph densities in graphons
In Pittel (1989)'s solution to a problem of Knuth (1976) on the expected number of stable matchings between $n$ men and $n$ women under uniform random preferences, it was shown that, as $n \to \infty$,...
10
votes
1
answer
549
views
Are there two-sided $\varepsilon$-expanders with independent sets of size $(1-\varepsilon)n$?
Terry Tao's notes on expander graphs has the following exercise:
Exercise 13 Let $G$ be a $k$-regular graph on $n$ vertices that is a two-sided $\epsilon$-expander for some $n > k \geq 1$ and $\...
10
votes
0
answers
616
views
Connections between Riemann hypothesis for curves over finite fields and Ramanujan property for graphs
this question relates to the beautiful construction of expander graphs using Cayley graphs of $PGL_2(\mathbb{F}_q)$, as exposited by Davidoff-Sarnak-Valette in their book, Elementary Number Theory, ...
10
votes
0
answers
522
views
Abelian sandpile models
This question is about a popular probabilistic model on graphs studied in physics, mostly, for the standard lattice in ${\mathbb R}^n$ but also on other graphs (this model is of the same spirit as ...
9
votes
0
answers
331
views
Embedding a graph into Euclidean space
I want to find a map $v\mapsto \tilde v$ from the vertex set of a connected infinite graph $\Gamma$ to a Euclidean space that meets the following two conditions:
there is $\varepsilon>0$ such that ...
9
votes
0
answers
308
views
Goldberg-Seymour conjecture
I am wondering whether the graph theory community regards the Goldberg-Seymour conjecture as settled. According to the Wikipedia entry on the Goldberg-Seymour conjecture, "In 2019, an alleged ...
9
votes
0
answers
340
views
How many orthogonal matrices (not orthonormal) are there with entries in $\{0,1,−1\}$?
Here by orthogonal matrix I mean just the rows are mutually orthogonal. Two such matrices are equivalent if one can be obtained from the other by permutations of rows and columns, or change of signs ...
9
votes
0
answers
305
views
Thurston on the Robertson-Seymour theorem
Danny Calegari recounts here that Bill Thurston "gave one talk explaining his idea of a new proof of (some version of) the Robertson-Seymour theorem" at MSRI in 1996-1997. I could not find it in the ...
9
votes
0
answers
258
views
How sensitive are Neural Networks to weight change?
Let's consider the space of feedforward neural networks with a given structure: $L$ layers, $m$ neurones per layer, ReLu activation, input dimension $d$, output dimension $k$.
Which means I'm ...
9
votes
0
answers
154
views
Minimal number of colours in distinguishing colouring of biconnected graphs
A colouring of edges of a graph is distingushing if no non-identity automorphism of the graph preserves this colouring.
Problem. Is it true that each biconnected graph possesses a distinguishing ...
9
votes
0
answers
155
views
Partitioning the vertices of a graph into induced trees
I am looking for previous work regarding graphs whose vertices can be assigned colours (not necessarily a proper colouring) in such a way that each colour class induces a tree.
In particular I am ...
9
votes
0
answers
520
views
Mysterious relationship between central charges of conformal field theories and the Beraha numbers
Background:
Conformal field theories (CFTs) in two dimensions are partially characterized by a so-called central charge (characterizing the central extension of the Virasoro algebra which defines it)....
9
votes
0
answers
224
views
Heuristic arguments regarding Sheehan's conjecture?
Sheehan conjectured that there are no 4-regular graphs that are uniquely hamiltonian (i.e. have exactly one hamilton cycle).
Evidence that might be loosely seen to be in favour of this conjecture is: ...
9
votes
0
answers
175
views
Cycles of length $2^n - 2$ in the De Bruijn graph
It is well known that the number of (cyclic) De Bruijn sequences is $2^{2^{n-1}-n}$. This number may also be interpreted as the number of cycles of length $2^n$ in the De Bruijn graph of order $n$.
...
9
votes
0
answers
492
views
A separation property of graphs of bounded tree-width
The following separation property of trees is well-known and in fact easy to prove (see e.g. the paper "Covering a hypergraph of subgraphs" by Noga Alon, Lemma 2.2)
Let $T$ be a tree and $r, m$ non-...
9
votes
0
answers
242
views
De Bruijn sequence inside De Bruijn sequence
A binary De Bruijn sequence of index $n$ is a circular sequence $S=a_1a_2\ldots a_{2^n}$, with $a_i∈\{0,1\}$, and such that each of the $2^n$ binary $n$-tuples occurs exactly once in $S$.
What is ...
9
votes
0
answers
291
views
Mapping graphs to ordinals
Robertson-Seymour theorem implies that graph minor relation is a well-quasi-ordering, which means (among other things) that this relation can be extended to a well-order, and other result says that ...
8
votes
0
answers
155
views
Hamiltonian paths in the prime sum graph
The following is a generalization of this old question .
Let $n\ge 2$, $[n]=\{1,\ldots,n\}$. For which distinct $a,b\in[n]$ is it possible to list $[n]$ in some order $x_1,\ldots,x_n$ such that $x_1=a$...
8
votes
0
answers
438
views
Extension of Erdős-Gallai (s,t)-path theorem to directed graphs
The following is a result of Erdős-Gallai from 1959 (https://link.springer.com/article/10.1007/BF02024498):
Given a 2-connected undirected unweighted graph with minimum degree at least $d$, for every ...
8
votes
0
answers
149
views
Partial order on graphs induced by homomorphism counts
For graphs $F$ and $G$, let $\hom(F,G)$ denote the number of homomorphisms (adjacency preserving maps) from $F$ to $G$. Define a relation $\le_{\hom}$ on (isomorphism classes of) graphs as $G \le_{\...
8
votes
0
answers
317
views
Explicit constructions of Ramanujan graphs
I am trying to find a list of all the explicit constructions of Ramanujan graphs. By a Ramanujan graph I mean a $k$-regular multi-graph $G$ such that all the non-trivial eigenvalues $\lambda$ of the ...
8
votes
0
answers
244
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 ...
8
votes
0
answers
256
views
Maximum number of cycles on regular graphs
Let $G$ be a $d$-regular graph on $n$ vertices. I'm interested in upper bounds on the number of cycles of length $k$ that hold for any such $G$. The regime I'm interested in is:
$d$ is fixed, and $...
8
votes
0
answers
225
views
On the structure of maximal Ramsey colorings
For positive integers $a_1,\dots,a_n$, recall that the multicolor Ramsey number $R(a_1,\dots,a_n)$ is the smallest integer $N$ such that if the edges of the complete graph $K_N$ are colored with the $...
8
votes
0
answers
241
views
Sum of perfect matching construction
Suppose we have two bipartite graphs $G_1$ and $G_2$ with perfect matching count $P_1$ and $P_2$ respectively then their disjoint union gives a bipartite graph with perfect matching $P_1P_2$.
Is ...
8
votes
0
answers
401
views
Parity of oriented rooted trees
Suppose we have a planar graf with vertices $v_o, \ldots, v_n$, where $n$ is even such that if we checkerboard-color regions in the complement, then the black regions are $n$ (non-degenerated) ...
8
votes
0
answers
175
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.
...
8
votes
0
answers
211
views
Has anyone implemented a circle graph recognition algorithm?
A double occurrence word is a circular string of length $2n$ over an alphabet of size $n$ with each letter occurring exactly twice, for example:
ABACCDBD
Given a ...
8
votes
0
answers
63
views
Color edges of graph w/r/t large induced subgraphs
Can we color the edges of any graph $G$ on $2m-1$ vertices with two colors such that any induced subgraph with at least $m$ edges is non-monochromatic?
If true, this would be sharp as shown by the ...
8
votes
0
answers
432
views
Is there a version of Weyl's law for graph Laplacians?
Is there a version of Weyl's law or a local Weyl's law for eigenvectors of the graph Laplacian?
For some context, a colleague in statistics has encountered eigenvectors of the Laplacian for certain ...
8
votes
0
answers
949
views
$R(3,6) = 18$, especially proving that $R(3,6)>17$
I'm studying the Ramsey numbers, especially $R(3,6) = 18$
I understand that the proof using the theorem $R(m,n) <R(m-1,n)+R(m,n-1)$ can only prove that $R(3,6)<20$. However by Cariolaro's "On ...
8
votes
0
answers
360
views
A question related to Conways 99 graph problem
I have observed that the number of triangles $\frac{vk}{6}$ of a strongly regular graph with parameters $(v,k,1,2)$ is given by the coefficient $2(k-1)$ in the molien series of the "4-D extraspecial ...
8
votes
0
answers
258
views
Shift on trivalent directed tree, operator and von Neumann algebra
Let $\mathcal{T}$ be the trivalent directed tree, with two parents and one child for each vertex (see below). Let $\mathcal{V}$ be the set of vertices of $\mathcal{T}$ and $H$ be the Hilbert space $\...
8
votes
0
answers
122
views
Is there a non-bipartite hamiltonian cubic graph on $n$ vertices with no $(n-1)$-cycle?
Is there a cubic (3-regular) graph $G$ on $n$ vertices such that:
$G$ is hamiltonian
$G$ has no $(n-1)$-cycles
$G$ is not bipartite
My computer tells me that there are none on up to $24$ vertices.
8
votes
0
answers
430
views
Is there an "Erlangen Program" for Graph Theory?
There are certain graph theoretic problems (especially optimization problems), whose solution-subgraph (i.e. the set of vertices and edges)), is invariant under certain modifications (especially ...
8
votes
0
answers
149
views
Edge-colorings of plane graphs: do you know references where the following questions are studied?
Let $G$ be a plane graph (or more generally, a graph embedded on a surface) with a proper edge-coloring of $G$ with $k$ colors $\{1,\ldots,k\}$. I am interested in studying the cyclic permutations of ...
8
votes
0
answers
200
views
Subgraphs of planar trivalent graphs
Let's think about planar trivalent graphs. (Or you can dualize and think about triangulations if you prefer.) It's easy to come up with a list of 'planar trivalent graphs with boundary' such that at ...
8
votes
0
answers
196
views
What is the probability of interpolating the Tutte polynomial of a planar graph from the values at the two hyperbolas?
The Tutte polynomial
is a bivariate polynomial with positive integer coefficient which is a graph
invariant and can be defined recursively.
Evaluating it is $\#P$-complete even when restricted to (...
8
votes
0
answers
414
views
One more coloring question
This question is related to my previous questions, say, this one and this one. Let $G$ be an infinite graph of bounded degree, and $\lambda>0$. Let $k=k_G(\lambda)$ be the minimal number of colors ...
8
votes
0
answers
850
views
Decomposition of graphs as symmetric differences of copies of $K_{a,b}$
I was wondering if the following decomposition of graphs has been studied, whether it has a name, and what the literature might be on it.
Given a labelled graph G, we decompose its edge-set as a ...
8
votes
0
answers
427
views
An extremal problem for graphs having every edge contained in a 4-clique
This is a follow-up to Graphs with many triangles but few complete graphs on 4 vertices
I'm looking for an upper bound for the difference between the number of edges and the number of 4-cliques in a ...
8
votes
0
answers
2k
views
What is the best lower bound for the domination number in regular graphs of girth 5?
The following theorem is a classical result (see [Alon and Spencer, The probabilistic method, 2nd ed., Theorem 1.2.2]):
Theorem: Let $G$ be a graph on $n$ vertices with minimum degree $d$. Then $G$ ...