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
Filter by
Sorted by
Tagged with
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 ...
Mikhail Tikhomirov's user avatar
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 ...
Ethan Splaver's user avatar
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-...
Mario Krenn's user avatar
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, ...
Dominic van der Zypen's user avatar
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 ...
Fedor Petrov's user avatar
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 "...
co.sine's user avatar
  • 403
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 ...
David Roberson's user avatar
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, ...
NageebAli's user avatar
  • 101
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$,...
Yufei Zhao's user avatar
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 $\...
JeremyKun's user avatar
  • 726
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, ...
David Jordan's user avatar
  • 6,053
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 ...
user avatar
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 ...
Anton Petrunin's user avatar
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 ...
James Propp's user avatar
  • 19.4k
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 ...
Arun 's user avatar
  • 725
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 ...
Arnaud's user avatar
  • 930
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 ...
Alfred's user avatar
  • 879
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 ...
Lviv Scottish Book's user avatar
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 ...
Gordon Royle's user avatar
  • 12.3k
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)....
Ruben Verresen's user avatar
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: ...
Gordon Royle's user avatar
  • 12.3k
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$. ...
Timothy Chow's user avatar
  • 78.1k
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-...
monkeymaths's user avatar
  • 1,169
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 ...
Alexey Ustinov's user avatar
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 ...
Wojowu's user avatar
  • 27.4k
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$...
Brendan McKay's user avatar
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 ...
Nicole Wein's user avatar
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_{\...
David Roberson's user avatar
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 ...
richarddedekind's user avatar
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 ...
Anton Petrunin's user avatar
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 $...
RegularGraph's user avatar
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 $...
Andrés E. Caicedo's user avatar
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 ...
Turbo's user avatar
  • 13.7k
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) ...
user avatar
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. ...
Florian Lehner's user avatar
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 ...
Gordon Royle's user avatar
  • 12.3k
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 ...
domotorp's user avatar
  • 18.3k
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 ...
Gabe K's user avatar
  • 5,364
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 ...
Janeth Benavides's user avatar
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 ...
user avatar
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 $\...
Sebastien Palcoux's user avatar
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.
Gordon Royle's user avatar
  • 12.3k
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 ...
Manfred Weis's user avatar
  • 12.6k
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 ...
Florent Foucaud's user avatar
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 ...
Scott Morrison's user avatar
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 (...
joro's user avatar
  • 24.2k
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 ...
user avatar
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 ...
Niel de Beaudrap's user avatar
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 ...
Thomas Kalinowski's user avatar
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$ ...
Florent Foucaud's user avatar

1
2
3 4 5
30