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.
548 questions
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 ...
- 12.7k
28
votes
8
answers
6k
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$...
- 4,014
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 ...
- 10.5k
21
votes
2
answers
4k
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 ...
- 155
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.
...
- 155
7
votes
1
answer
760
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 ...
- 123
4
votes
3
answers
606
views
Why is this bipartite graph a partial cube, if it is?
Since the set $\{\log(p) \mid p \text{ is prime, } p \le n \}$ for a natural number $n$ is $\mathbb{Q}$-linear independent and since:
$$\log(m) = \sum_{p\mid m} v_p(m) \log(p)$$
we can view each $\log(...
- 3,064
3
votes
2
answers
331
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$, ...
- 20.2k
22
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?
- 9,720
3
votes
1
answer
573
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 ...
- 13.6k
2
votes
3
answers
758
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 {\...
- 48.9k
19
votes
4
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 ...
- 3,463
72
votes
9
answers
9k
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 ...
- 6,034
63
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 ...
49
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 ...
47
votes
15
answers
29k
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 ...
45
votes
5
answers
64k
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 ...
- 3,630
39
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,...
- 4,757
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.
...
- 236k
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 ...
- 82.7k
28
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
...
- 16.2k
26
votes
4
answers
2k
views
What relationship, if any, is there between the diameter of the Cayley graph and the average distance between group elements?
It's known that every position of Rubik's cube can be solved in 20 moves or less. That page includes a nice table of the number of positions of Rubik's cube which can be solved in k moves, for $k = 0,...
- 14k
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 ...
- 6,917
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 ...
- 151k
24
votes
4
answers
36k
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 ...
- 1,250
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 ...
- 1,164
21
votes
4
answers
14k
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?
- 431
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 ...
- 6,523
16
votes
3
answers
720
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 $...
- 13.6k
16
votes
3
answers
2k
views
Are infinite planar graphs still 4-colorable?
Imagine you have a finite number of "sites" $S$ in the positive quadrant
of the integer lattice $\mathbb{Z}^2$,
and from each site $s \in S$, one connects $s$ to every lattice point to which it
has a ...
- 151k
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.
- 175
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 ...
- 718
12
votes
1
answer
510
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, ...
- 175
11
votes
2
answers
1k
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 ...
- 13.2k
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.
- 159
6
votes
2
answers
2k
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 ...
- 288
5
votes
3
answers
411
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 ...
- 1,444
2
votes
1
answer
401
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?
- 48.9k
1
vote
0
answers
185
views
Maximum independent set in dense graphs
Let $0 < A < 1$ and $G$ be connected d-regular graph
with degree $d=[A n]$. The density of $G$ is about $A$.
Q1 Are there constraints on $A$ such that finding maximum
independent set of $G$ is ...
- 25.4k
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 ...
- 421
-2
votes
1
answer
121
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?
- 48.9k
69
votes
7
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 ...
64
votes
5
answers
15k
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. ...
- 290
57
votes
4
answers
15k
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 ...
- 7,857
56
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 ...
- 236k
40
votes
7
answers
9k
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 ...
- 9,720
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; ...
- 24.7k
34
votes
18
answers
20k
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 ...
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 ...
- 349