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,150
questions
23
votes
0
answers
482
views
Is the Poset of Graphs Automorphism-free?
For $n\geq 5$, let $\mathcal {P}_n$ be the set of all isomorphism classes of graphs with n vertices. Give this set the poset structure given by $G \le H$ if and only if $G$ is a subgraph of $H$.
Is ...
22
votes
11
answers
4k
views
What are some good examples of non-monotone graph properties?
It seems that many, if not almost all, of the properties studied in graph theory are monotone. (Property means it is invariant under permutation of vertices, and monotone means that the property is ...
22
votes
4
answers
3k
views
Brute force open problems in graph theory
Usually, a graph theoretic problem asks whether some class of graphs $C$ possesses a quality $P$. For example, $C$ is the class of all graphs and $P$ is the reconstructability property in Kelly-Ulam ...
22
votes
5
answers
4k
views
Collection of conjectures and open problems in graph theory
Is there something similar to the Kourovka Notebook for graph theory (or anyway an organized, possibly commented, collection of conjectures and open problems)?
22
votes
6
answers
5k
views
The matrix tree theorem for weighted graphs
I am interested in the general form of the Kirchoff Matrix Tree Theorem for weighted graphs, and in particular what interesting weightings one can choose.
Let $G = (V,E, \omega)$ be a weighted graph ...
22
votes
2
answers
879
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 ...
22
votes
2
answers
8k
views
Cubic graphs without a perfect matching and a vertex incident to three bridges
The example shown below (courtesy of David Eppstein) is a common example of a cubic graph that admits no perfect matching:
(source: uci.edu)
Are there other examples of cubic graphs that do not ...
22
votes
3
answers
1k
views
Which paths in a graph are orthogonal to all cycles?
Start with some standard stuff. Suppose we have a directed graph $\Gamma$. I'll write $e : v \to w \,$ when $e$ is an edge going from the vertex $v$ to the vertex $w$. We get a vector space of 0-...
22
votes
2
answers
1k
views
Graphs, K-theory and combinatorial balls: conjectures
The following conjectures from Kapranov and Saito's Hidden Stasheff polytopes in algebraic K-theory and in the space of Morse functions aren't as well-known as they aught to be, so I'd like to state ...
22
votes
2
answers
2k
views
Largest graphs of girth at least 6
Let $e_6(n)$ be the greatest number of edges in a simple graph with $n$ vertices and girth at least 6.
Let $G_6(n)$ be the set of simple graphs of order $n$ with girth at least 6 and $e_6(n)$ edges.
...
22
votes
0
answers
539
views
Zero curves of Tutte Polynomials?
There is an extensive theory of the real and complex roots of the chromatic polynomial of a graph, a substantial fraction of this being due to the connections between the chromatic polynomial and a ...
21
votes
10
answers
4k
views
Why do we associate a graph to a ring? [closed]
I don't know if it is suitable for MathOverflow, if not please direct it to suitable sites.
I don't understand the following:
I find that there are many ways a graph is associated with an algebraic ...
21
votes
7
answers
1k
views
Reference for topological graph theory (research / problem-oriented)
I would be interested in recommendations for topological graph theory texts. I think Gross and Yellen has a great chapter on topological graph theory, and I find Mohar and Thomassen's Graphs on ...
21
votes
3
answers
2k
views
Obstructions for embedding a graph on a surface of genus g
Kuratowski's theorem tells us the complete graph $K_5$ and the bipartite graph $K_{3,3}$ are the only obstructions to a graph being planar, ie embeddable in the plane with no edge-crossings.
Is the ...
21
votes
8
answers
8k
views
Why is edge-coloring less interesting than vertex-coloring?
I was wondering why there is (apparently) much more research directed towards vertex-coloring than edge-coloring? Prima facie, it seems that edge-coloring is just as "natural" a thing to investigate.
...
21
votes
2
answers
1k
views
Why are the numbers counting "ever-closer" lattice paths so round?
Let $u(i,j)$ denote the number of lattice paths from the origin to a fixed terminal point $(i,j)$ subject only to the condition that each successive lattice point on the path is closer to $(i,j)$ than ...
21
votes
4
answers
13k
views
How many $p$-regular graphs with $n$ vertices are there?
Suppose that there are $n$ vertices, we want to construct a regular graph with degree $p$, which, of course, is less than $n$. My question is how many possible such graphs can we get?
21
votes
4
answers
3k
views
Can you determine whether a graph is the 1-skeleton of a polytope?
How do I test whether a given undirected graph is the 1-skeleton of a polytope?
How can I tell the dimension of a given 1-skeleton?
21
votes
3
answers
3k
views
Cauchy-Schwarz proof of Sidorenko for 3-edge path (Blakley-Roy inequality)
Is there a "Cauchy-Schwarz proof" of the following inequality?
Theorem. Given $f \colon [0,1]^2 \to [0,1]$, one has
$$
\int_{[0,1]^4} f(x,y)f(z,y)f(z,w) \, dxdydzdw \geq \left(\int_{[0,1]^2} f(x,y) \,...
21
votes
2
answers
3k
views
Graphs with only disjoint perfect matchings
Let $G(V,E)$ be a graph. I am searching for graphs with only disjoint perfect matchings (i.e. every edge only appears in at most one of the perfect matchings).
Examples:
Cyclic graph $C_n$ with even ...
21
votes
3
answers
1k
views
Probability that random weights on $K_n$ satisfy triangle inequality
Given $K_n$, if a random real weight between $[0, 1]$ is chosen for every edge, what is the probability that the graph satisfies the triangle inequality? How about the discrete version, where the ...
21
votes
6
answers
3k
views
"The" random tree
One time I heard a talk about "the" random tree. This tree has one vertex for each natural number, and the edges are constructed probabilistically. Connect vertex $2$ to vertex $1$. Connect vertex $3$ ...
21
votes
2
answers
3k
views
Is there a graph with 99 vertices in which every edge belong to a unique triangle and every nonedge to a unique quadrilateral?
99-Graph: Is there a graph with 99 vertices in which every edge (i.e. pair of joined vertices) belong to a unique triangle and every nonedge (pair of unjoined vertices) to a unique quadrilateral?
21
votes
4
answers
1k
views
A graph with few edges everywhere
Given a graph $G(V,E)$ whose edges are colored in two colors: red and blue.
Suppose the following two conditions hold:
for any $S\subseteq V$, there are at most $O(|S|)$ red edges in $G[S]$
for any $...
21
votes
2
answers
1k
views
The chromatic number of the union of two graphs
Let $G_n$ be the graph on the set of all binary strings of length $n$ with two strings adjacent whenever they are Hamming distance $2$ away from each other, or one of them lies below another one; thus,...
21
votes
2
answers
900
views
Seymour's second neighborhood conjecture for infinite graphs
Let $G$ be a directed graph (say simple, so no loops and each pair of vertices has at most one directed edge between them). Suppose $G$ is 'locally finite', in the sense that each vertex has only ...
21
votes
3
answers
1k
views
Why are Dynkin diagrams characterized by their eigenvalues?
The Dynkin diagrams An, Dn, E6,
E7, E8 can be characterized among finite simple connected
graphs by the property that their eigenvalues (that is, the eigenvalues of their adjacency matrices) all have ...
21
votes
5
answers
1k
views
Spectral theory of graph Laplacian besides $\lambda_2$
Most of what I've seen about the spectral theory of the graph Laplacian concentrates on $\lambda_2$, the second-smallest eigenvalue. This eigenvalue contains information regarding the connectivity of ...
21
votes
1
answer
1k
views
A strange sum over bipartite graphs
While mucking around with some generating functions related to enumeration of regular bipartite graphs, I stumbled across the following cutie. I wonder if anyone has seen it before, and/or if anyone ...
21
votes
1
answer
764
views
Girth of the symmetric group
Let $n \in \mathbb N$ and $\{\sigma,\tau\} \subset {\rm Sym}(n)$ be a generating set.
Question: What is the maximal possible girth (if one varies $\sigma, \tau$) of the associated Cayley graph?
I ...
21
votes
2
answers
4k
views
Fast Fourier transform for graph Laplacian?
In the case of a regularly-sampled scalar-valued signal $f$ on the real line, we can construct a discrete linear operator $A$ such that $A(f)$ approximates $\partial^2 f / \partial x^2$. One way to ...
21
votes
2
answers
459
views
Labeling binary trees so that adjacent vertices differ by a power of two
Let $T$ be a finite rooted binary tree (where "binary tree" means that each node has at most two children, possibly less) with $n$ nodes in total. Is there a labeling of the nodes of $T$ with the ...
21
votes
1
answer
1k
views
Monomer-Dimer tatami tilings need better relationships with other math. Summary of results
A monomer-dimer tiling of a rectangular grid with $r$ rows and $c$ columns satisfies the tatami condition if no four tiles meet at any point. (Or you can think of it as the removal of a matching from ...
21
votes
1
answer
1k
views
Red-blue alternating paths
Suppose we have two simple graphs on the same vertex set. We will call one of them red, the other blue. Suppose that for $i=1,..,k$ we have $deg (v_i)\ge i$ in both graphs, where $V_k=\{v_1,\ldots,v_k\...
21
votes
0
answers
425
views
Straight-line drawing of regular polyhedra
Find the minimum number of straight lines needed to cover a crossing-free straight-line drawing of the icosahedron $(13\dots 15)$ and of the dodecahedron $(9\dots 10)$ (in the plane).
For example, ...
20
votes
13
answers
4k
views
Local-global approach to graph theory
This question is inspired from
(i) Theorems like the "universal friend theorem": If every two vertices in a connected graph $G$ share a unique common neighbor, then there is a vertex connected to all ...
20
votes
5
answers
2k
views
The middle eigenvalues of an undirected graph
Let $ \lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_{2n} $
be the collection of eigenvalues of an adjacency matrix of an undirected graph $G$ on $2n$ vertices. I am looking for any work or references ...
20
votes
6
answers
861
views
Hamiltonian paths where the vertices are integer partitions
I have been working on this problem for several months now but have not made much progress. It concerns the set of all integer partitions of n.
Let the vertices of the graph G=G(n) denote all the p(n) ...
20
votes
3
answers
968
views
Does the hypergraph of subgroups determine a group?
A hypergraph is a pair $H=(V,E)$ where $V\neq \emptyset$ is a set and $E\subseteq{\cal P}(V)$ is a collection of subsets of $V$. We say two hypergraphs $H_i=(V_i, E_i)$ for $i=1,2$ are isomorphic if ...
20
votes
2
answers
1k
views
Erdős, Harary, Tutte's "dimension of graph": Progress in last 48 yrs?
I just ran across this delightful paper by an amazing triumvirate:
Paul Erdős, Frank Harary, and William Tutte. "On the dimension of a graph." Mathematika 12.118-122 (1965): 20.
(Cambridge link)
...
20
votes
4
answers
2k
views
What algebraic structures are related to the McGee graph?
Recall that an $(n,g)$-graph is a simple graph where each node has $n$ neighbors and the shortest cycle has length $g$, while an $(n,g)$-cage is $(n,g)$-graph with the minimum number of nodes.
The ...
20
votes
1
answer
4k
views
What have simplicial complexes ever done for graph theory?
(I am asking in a somewhat tongue-in-cheek fashion, of course, but nevertheless...)
Are there examples of results in "classical" [*] graph theory that have
been achieved by using simplicial ...
20
votes
2
answers
1k
views
Non-definability of graph 3-colorability in first-order logic
What is a proof that graph 3-colorability is not definable in first order logic? Where did it first appear?
20
votes
3
answers
1k
views
Can a 3-regular non-1-planar graph be constructed?
A $1$-planar graph is a graph which has a drawing on the plane such that each edge has at most one crossing.
I used nauty to generate all 3-regular graphs up to ...
20
votes
3
answers
3k
views
Proofs of parity results via the Handshaking lemma
I particularly like the following strategy to prove that the number of some combinatorial objects is even: to construct a graph, in which they correspond to vertices of odd degree (=valency).
Let me ...
20
votes
1
answer
1k
views
A Ramsey avoidance game
Consider the following game: Given $K_n$ the complete graph on $n$ vertices, two players take turns coloring its edges. Initially no edges are colored. At his turn a player can color a prevoiusly not ...
20
votes
1
answer
4k
views
Where can I find Gonthier's Coq code proving the four color theorem?
In a 2008 article in the Notices, Georges Gonthier announced a computer-checked proof of the four color theorem using Coq:
Gonthier, Georges. Formal proof—the four-color theorem.
Notices Amer. ...
20
votes
2
answers
866
views
Is there an analogue of the Erdős–Gallai theorem for simplicial complexes?
The Erdős–Gallai theorem gives a necessary and sufficient condition for a finite sequence of natural numbers to be the degree sequence of a simple graph.
In particular $d_1 \ge d_2 \ge \dots \ge d_n$ ...
19
votes
8
answers
6k
views
Generating function in graph theory
I am looking for a simple illustration of generating functions in graph theory.
So far, the matching polynomial seems to be the best. But I want something bit richer; at least a derivative should ...
19
votes
5
answers
7k
views
What is the probability that two random walkers will meet?
It is a well known result that a random walk on a 2D lattice will return to the origin see Polya's random walk constant. Based on this, it is not a big stretch to conclude that the random walk will ...