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.

Filter by
Sorted by
Tagged with
46 votes
8 answers
5k views

Can a problem be simultaneously polynomial time and undecidable?

The Robertson-Seymour theorem on graph minors leads to some interesting conundrums. The theorem states that any minor-closed class of graphs can be described by a finite number of excluded minors. As ...
Gordon Royle's user avatar
  • 12.3k
27 votes
8 answers
5k views

Representability of finite metric spaces

There have been a couple questions recently regarding metric spaces, which got me thinking a bit about representation theorems for finite metric spaces. Suppose $X$ is a set equipped with a metric $d$...
Matt Noonan's user avatar
  • 3,984
11 votes
1 answer
2k views

Cycling through the Zeta Garden: Zeta functions for graphs, cycle index polynomials, and determinants

Zeta functions abound in mathematics. Audrey Terras describes in Zeta Functions and Chaos three zeta functions--the zeta fct. of a projective non-singular algebraic variety; the Artin-Mazur zeta ...
Tom Copeland's user avatar
  • 9,937
32 votes
0 answers
3k views

Vertex coloring inherited from perfect matchings (motivated by quantum physics)

Added (19.01.2021): Dustin Mixon wrote a blog post about the question where he reformulated and generalized the question. Added (25.12.2020): I made a youtube video to explain the question in detail. ...
Mario Krenn's user avatar
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 ...
Mario Krenn's user avatar
7 votes
1 answer
721 views

Difference Sets

Suppose $$ P \subseteq \{1,2,\dots,N\},\quad |P| = K $$ We calculate the differences as: $$d=p_i-p_j\mod N,\quad i\ne j$$ Now let $a_d$ denote the number of occurrence of $d$ (for $d = 1, 2, \dots , N ...
Mahdi Khosravi's user avatar
3 votes
2 answers
325 views

Existence of connected component with large boundary?

Question 1. Let $\Gamma=(V,E)$ be a connected graph with $n$ vertices, all of degree $d\geq 4$. Assume every vertex has $d$ distinct neighbors. (We can think of $d$ as being much smaller than $n$, ...
H A Helfgott's user avatar
  • 19.3k
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?
Hans-Peter Stricker's user avatar
3 votes
1 answer
529 views

Counting "connected" edge orderings (shellings) of the complete graph [duplicate]

This question is inspired by "Number of collinear ways to fill a grid" by Sebastien Palcoux and the comments of user44191 on this earlier question of Palcoux's. Let $G=(V,E)$ be a graph. An edge ...
j.c.'s user avatar
  • 13.5k
2 votes
3 answers
740 views

Mutually non-isomorphic connected graphs on $\kappa$ points

For any set $X$, let $[X]^2 = \big\{\{a,b\}: a, b\in X \land a\neq b\big\}$. Let $\kappa$ be an infinite cardinal. Is there a set ${\cal E} \subseteq {\cal P}([\kappa]^2)$ such that for all $E \in {\...
Dominic van der Zypen's user avatar
71 votes
9 answers
8k views

What is a continuous path?

I would like some help, because I am getting mad trying to answer the following Question: Let $X$ be a topological space, what is a continuous path in $X$? Well, maybe you're already getting ...
Valerio Capraro's user avatar
62 votes
19 answers
12k views

Generalizations of the four-color theorem

The four color theorem asserts that every planar graph can be properly colored by four colors. The purpose of this question is to collect generalizations, variations, and strengthenings of the four ...
50 votes
15 answers
11k views

Strengthening the induction hypothesis

Suppose you are trying to prove result $X$ by induction and are getting nowhere fast. One nice trick is to try to prove a stronger result $X'$ (that you don't really care about) by induction. This ...
44 votes
15 answers
28k views

What are the applications of hypergraphs?

Hypergraphs are like simple graphs, except that instead of having edges that only connect 2 vertices, their edges are sets of any number of vertices. This happens to mean that all graphs are just a ...
43 votes
5 answers
63k views

How large is TREE(3)?

Friedman, in _Lectures notes on enormous integers shows that TREE(3) is much larger than n(4), itself bounded below by $A^{A(187195)}(3)$ (where $A$ is the Ackerman function and exponentiation ...
Feldmann Denis's user avatar
38 votes
3 answers
5k views

Arranging numbers from $1$ to $n$ such that the sum of every two adjacent numbers is a perfect power

I've known that one can arrange all the numbers from $1$ to $\color{red}{15}$ in a row such that the sum of every two adjacent numbers is a perfect square. $$8,1,15,10,6,3,13,12,4,5,11,14,2,7,9$$ Also,...
mathlove's user avatar
  • 4,727
32 votes
9 answers
5k views

How many groups of size at most n are there? What is the asymptotic growth rate? And what of rings, fields, graphs, partial orders, etc.?

Question. How many (isomorphism types of) finite groups of size at most n are there? What is the asymptotic growth rate? And the same question for rings, fields, graphs, partial orders, etc. ...
Joel David Hamkins's user avatar
28 votes
3 answers
2k views

Is every positive integer the permanent of some 0-1 matrix?

In the course of discussing another MO question we realized that we did not know the answer to a more basic question, namely: Is it true that for every positive integer $k$ there exists a balanced ...
Timothy Chow's user avatar
  • 78.1k
27 votes
2 answers
3k views

Realizing groups as automorphism groups of graphs.

Frucht showed that every finite group is the automorphism group of a finite graph. The paper is here. The argument basically is that a group is the automorphism group of its (colored) Cayley graph ...
Stefan Geschke's user avatar
25 votes
3 answers
1k views

Algebraic graph invariant $\mu(G)$ which links Four-Color-Theorem with Schrödinger operators: further topological characterizations of graphs?

30 years ago, Yves Colin de Verdière introduced the algebraic graph invariant $\mu(G)$ for any undirected graph $G$, see [1]. It was motivated by the study of the second eigenvalue of certain ...
Claus's user avatar
  • 6,777
24 votes
4 answers
35k views

Finding a cycle of fixed length

Is there any result about the time complexity of finding a cycle of fixed length $k$ in a general graph? All I know is that Alon, Yuster and Zwick use a technique called "color-coding", which has a ...
Hsien-Chih Chang 張顯之's user avatar
24 votes
6 answers
3k views

Shortest grid-graph paths with random diagonal shortcuts

Suppose you have a network of edges connecting each integer lattice point in the 2D square grid $[0,n]^2$ to each of its (at most) four neighbors, {N,S,E,W}. Within each of the $n^2$ unit cells of ...
Joseph O'Rourke's user avatar
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 ...
Anthony Labarre's user avatar
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?
Youzhou Zhou's user avatar
18 votes
3 answers
1k views

Minimal graphs with a prescribed number of spanning trees

As it's long ago since Erdős died and MathOverflow is the second best alternative to him (for discussing personal problems), I'd like to start a fruitful discussion about the following problem that I ...
Jernej's user avatar
  • 3,433
17 votes
11 answers
2k views

Chromatic number of graphs of tangent closed balls

The Koebe–Andreev–Thurston theorem gives a characterization of planar graphs in terms of disjoint circles being tangent. For every planar graph $G$ there is a disk packing whose graph is $G$. What ...
Kristal Cantwell's user avatar
16 votes
3 answers
701 views

Can we realize a graph as the skeleton of a polytope that has the same symmetries?

Given a graph $G$, a realization of $G$ as a polytope is a convex polytope $P\subseteq \Bbb R^n$ with $G$ as its 1-skeleton. A realization $P\subseteq \Bbb R^n$ is said to realize the symmetries of $...
M. Winter's user avatar
  • 12.5k
14 votes
4 answers
3k views

Number of closed walks on an $n$-cube

Is there a known formula for the number of closed walks of length (exactly) $r$ on the $n$-cube? If not, what are the best known upper and lower bounds? [Edit] Note: the walk can repeat vertices.
Lev Reyzin's user avatar
13 votes
1 answer
2k views

Different uses of the word "ergodic"

There appear to be two definitions of the word ergodic. The dynamical systems definition says that a measure space $(X,\mathit B, \mu)$ and measure preserving transformation $T: X \mapsto X$ is ...
Daniel Mansfield's user avatar
12 votes
1 answer
483 views

Probability of a graph procedure

We are going to build $K_n$ one edge at a time. Begin with the empty graph on $n$ vertices. Take a random permutation of the edges of $K_n$ and, one at a time, place the edges onto the graph (so, ...
user43928's user avatar
  • 175
11 votes
2 answers
995 views

Densest Graphs with Unique Perfect Matching

Given a graph $G$ with $n$ vertices, that has a perfect matching $M$, what is the maximal number of edges that $G$ can have without contradicting the uniqueness of $M$? Are examples of such extremal ...
Manfred Weis's user avatar
  • 12.6k
10 votes
1 answer
1k views

How can we find n points on a plane so that as many pairs of points as possible have the same distance?

There are $n$ points on the plane, and we need to maximize the number of pairs of points which have the same Euclidean distance.
Cynasty's user avatar
  • 159
6 votes
2 answers
1k views

How to understand the combinatorial Laplacian $\Delta$ which is defined on the graph?

I have a question about the combinatorial Laplacian $\Delta$ which is defined by $$\Delta(u,v)=c(u)1_{u=v}-c(u,v)$$ where $u, v$ are some vertices in the graph $G=(V, E)$, and $c(u,v)$ is a ...
Hermi's user avatar
  • 274
5 votes
3 answers
394 views

Simple graphs with prescribed degrees as disjoint union of simple subgraphs with prescribed degrees

Consider a set $V$ of $n$ vertices, and three degree sequences $a_i$, $b_i$ and $c_i$ such that $c_i = a_i+b_i$, $i=1..n$. Assume these degree sequences are graphical: there exist simple graphs (no ...
Matthieu Latapy's user avatar
2 votes
1 answer
389 views

Perfect matchings in infinite graphs

Let $G=(V,E)$ be an infinite graph such that $|V| = \kappa$ for some infinite cardinal $\kappa$, and every $v\in V$ has degree $\kappa$. Does $G$ have a perfect matching?
Dominic van der Zypen's user avatar
0 votes
1 answer
1k views

Does this graph contain at least two Hamiltonian cycles?

Let $G$ be a simple graph which is a $2n$-cycle together with $n$ chords such that $G$ is $3$-regular. In other words, the set of $n$ chords is a perfect matching of $G$. I conjecture that for every ...
user40096's user avatar
  • 421
-2 votes
1 answer
115 views

Contracting non-adjacent points in the icosahedron [closed]

Are there $2$ non-adjacent points in the icosahedron graph $G$ such that contracting them leaves the Hadwiger number unchanged?
Dominic van der Zypen's user avatar
67 votes
6 answers
17k views

What is a chess piece mathematically?

Historically, the current "standard" set of chess pieces wasn't the only existing alternative or even the standard one. For instance, the famous Al-Suli's Diamond Problem (which remained ...
Morteza Azad's user avatar
61 votes
5 answers
11k views

Intuitively, what does a graph Laplacian represent?

Recently I saw an MO post Algebraic graph invariant $\mu(G)$ which links Four-Color-Theorem with Schrödinger operators: further topological characterizations of graphs? that got me interested. ...
GraphX's user avatar
  • 260
56 votes
4 answers
14k views

Connectivity of the Erdős–Rényi random graph

It is well-known that if $\omega=\omega(n)$ is any function such that $\omega \to \infty$ as $n \to \infty$, and if $p \ge (\log{n}+\omega) / n$ then the Erdős–Rényi random graph $G(n,p)$ is ...
Matthew Kahle's user avatar
55 votes
21 answers
14k views

Linear algebra proofs in combinatorics?

Simple linear algebra methods are a surprisingly powerful tool to prove combinatorial results. Some examples of combinatorial theorems with linear algebra proofs are the (weak) perfect graph theorem, ...
47 votes
7 answers
5k views

Is it easy to produce hard-to-color graphs?

This question arises from my recent visit to my daughter's second-grade class, where I led some discussion and activities on graph coloring (see Math for seven-year-olds). In one such activity, each ...
Joel David Hamkins's user avatar
39 votes
7 answers
8k views

Spectral graph theory: Interpretability of eigenvalues and -vectors

I thought "Wow!" when I learned that the eigenvector of the adjacency matrix of a cycle graph $C_n$ corresponding to the second largest eigenvalue gives the coordinates of the vertices when equally ...
Hans-Peter Stricker's user avatar
36 votes
21 answers
6k views

Generalizations of Planar Graphs

This is a follow up to Harrison's question: why planar graphs are so exceptional. I would like to ask about (and collect answers to) various notions, in graph theory and beyond graph theory (topology; ...
Gil Kalai's user avatar
  • 24.2k
34 votes
9 answers
7k views

Applications of infinite graph theory

Finite graph theory abounds with applications inside mathematics itself, in computer science, and engineering. Therefore, I find it naturally to do research in graph theory and I also clearly see the ...
Richard Dupont's user avatar
34 votes
18 answers
19k views

Interesting and accessible topics in graph theory

This summer, I will be teaching an introductory course in graph theory to talented high school seniors. The intent of the course is not to establish proficiency in graph theory, per se. Rather, I hope ...
33 votes
10 answers
6k views

Is the empty graph a tree?

This is a boring, technical question that I stumbled upon while making a contribution to Sage. I would still like to hear a constructive answer so hopefully the question does not get closed. The ...
Jernej's user avatar
  • 3,433
33 votes
1 answer
1k views

What does this connection between Chebyshev, Ramanujan, Ihara and Riemann mean?

It all started with Chris' answer saying returning paths on cubic graphs without backtracking can be expressed by the following recursion relation: $$p_{r+1}(a) = ap_r(a)-2p_{r-1}(a)$$ $a$ is an ...
draks ...'s user avatar
  • 457
31 votes
3 answers
2k views

Has there been a computer search for a 5-chromatic unit distance graph?

The existence of a 4-chromatic unit distance graph (e.g., the Moser spindle) establishes a lower bound of 4 for the chromatic number of the plane (see the Nelson-Hadwiger problem). Obviously, it ...
Juho's user avatar
  • 717
30 votes
4 answers
4k views

Adjacency matrices of graphs

Motivated by the apparent lack of possible classification of integer matrices up to conjugation (see here) and by a question about possible complete graph invariants (see here), let me ask the ...
Andreas Thom's user avatar
  • 25.3k

1
2 3 4 5
11