Questions tagged [extremal-graph-theory]
Study of graphs satisfying a property that are maximal or minimal with respect to some parameter. A classic example is Turán's Theorem, which exactly characterizes the densest graphs on $n$ vertices without a $K_t$ subgraph.
253 questions
11
votes
5
answers
2k
views
Are all almost regular graphs obvious?
Let the maximum and minimum degress of a graph be denoted (as usual) by $\Delta$ and $\delta$ respectively.
A graph is almost regular if $\Delta-\delta=1$.
Now, here is a simple way to generate ...
- 6,962
5
votes
2
answers
383
views
Extremal graph theory for directed graphs
In extremal graph theory, there are results such as
$$t(C_4,G)\geq t(K_2,G)^4,$$
where $G$ is an undirected graph, $C_4$ is a cycle graph on 4 nodes, $K_2$ is a complete graph of $2$ nodes, and $t(\...
- 131
7
votes
4
answers
950
views
Extremal examples for a folklore lemma on subgraphs of large minimum degree
It's a well known fact that a graph $G$ of average degree $d$ has a subgraph $G'$ of minimum degree at least $d/2$ and that the constant $1/2$ cannot be improved. The proof I know, which proceeds by ...
- 543
18
votes
2
answers
3k
views
Determine or estimate the number of maximal triangle-free graphs on $n$ vertices
Among the collections of the open problems of Paul Erdős on the website of
Professor Fan Chung, there is one called "number of triangle-free graphs".
http://www.math.ucsd.edu/~erdosproblems/erdos/...
user39815
6
votes
1
answer
243
views
Hamiltonicity criteria for sparse graphs
Given a sparse graph, how can one go about proving that it is Hamiltonian? (Assuming it actually is, of course).
There are three main classes of criteria for Hamiltonicity that I am aware of:
Dirac-...
- 6,962
13
votes
2
answers
870
views
Strongly connected directed graphs with large directed diameter and small undirected diameter?
This question is an attempt to make progress on domotorp's interesting challenge. This question was originally asked in two parts; the former of which was answered by Ilya Bogdanov, and the latter of ...
- 156k
4
votes
1
answer
437
views
Extremal functions for tournaments
We are looking at directed graphs with no loops or parallel edges, but given two vertices $x$ and $y$, we allow the presence of both the edge $(x, y)$ and $(y, x)$. Thus, if $G$ is a directed graph ...
- 677
0
votes
1
answer
431
views
Efficient isomorphic subgraph matching with similarity scores
I'm a computer vision PhD student, and I'm looking for an efficient approximation to the following problem, which could end up helping in image to image matching. Failing that, pointers to relevant ...
- 223
2
votes
0
answers
301
views
The Turán problem for graphs with given chromatic number
The ordinary Turán problem for graphs asks, "Given a graph $H$, if $G$ is an $H$-free graph on $n$ vertices, what is the largest number of edges that $G$ can have?" As is well known, if $\chi(H) = r +...
- 462
6
votes
1
answer
582
views
On Turan's theorem
Turan's theorem provides minimum number of edges of a graph on $n$ vertices to surely contain a clique of a prescribed size. This has been generalized to regular graphs.
What additional ...
- 13.9k
6
votes
1
answer
796
views
No big clique minor but a big grid minor
I was wondering if the following result is known (or if there's a nice short proof without treewidth/brenchwidth related theorems): as the title says, suppose you have a graph without a big clique ...
- 625
11
votes
0
answers
310
views
How many n/2-cycles can a cubic graph have
Given a simple cubic graph with $n$ vertices (which implies that $n$ is even), what is a good upper bound on the number of cycles of length $n/2$ it can have?
A random cubic graph has $\Theta((4/3)^n/...
- 37.7k
2
votes
0
answers
285
views
Bipartite independence number
Consider a balanced bipartite graph $G=(U,V,E)$, i.e., a bipartite graph with $|U|=|V|$. An independent set $I$ of $G$ is balanced if $|I \cap U| = |I \cap V|$.
The bipartite independence number of $...
- 418
6
votes
2
answers
863
views
Minimal graphs of prescribed girth and chromatic number
The well known result of Erdős, states that
Given integers $g > 2$ and $k > 1$ there exist a graph $G$ with $\chi(G) \geq k$ and girth at least $g.$
What I am wondering is
When can we ...
- 3,463
12
votes
1
answer
850
views
How to find or constrain "particularly good" (two-sided) spectral expanders?
I'm new to graph theory, but a response to a question I asked a while ago introduced me to the concept of expander graphs.
A k-regular graph (henceforth "graph") on n nodes has eigenvalues k = λ1 ≥ ...
- 3,612
6
votes
2
answers
317
views
Is there a graph that is Ramsey for $P_{2n}$ but is $C_{2n+1}-$free
Write $F\to G$ to mean that for every two coloring of the edges of $F$, there exists a monochromatic copy of $G$. Nešetřil and Rödl proved that for every graph $G$, there exists a graph $F$ such that ...
- 61
2
votes
2
answers
1k
views
Random graphs require O(n log(n)) edges until they are almost certainly fully connected - what are more concrete boundaries ?
As far as I understand my literature, the probability of a random graph being fully connected tends toward one as the number of edges approaches a value of size $O(n \log(n))$
The way I read this, ...
- 21
4
votes
1
answer
1k
views
Complete Bipartite Subgraph of Dense Bipartite Subgraph
Q1: Consider a $2^n$ by $2^n$ bipartite graph with at least $(1-\epsilon)2^{2n}$ edges. For any $\epsilon > 0$ and $n$ large enough, is it always possible to find a $2^{(1-f(\epsilon))n}$ by $2^{(1-...
- 41
1
vote
1
answer
175
views
Distribution of Induced Subgraphs of Extremal Ramsey Graphs
Choose $k$. Let $G = (V,E)$ be a graph on $n = R(k,k)-1$ vertices (that is, $G$ is an extremal example for $R(k,k)$, and $g : E \to \{r, b\}$ be an edge 2-coloring such that there is no monochromatic $...
- 316
4
votes
2
answers
1k
views
Maximum number of edges $f(n,k)$ in a graph on $n$ vertices with no $k$-core?
The $k$-core of a finite graph is defined as follows. Delete all vertices of degree $< k$ and repeat until there are no such vertices left. If there is a nonempty subgraph remaining, necessarily ...
- 7,857
1
vote
1
answer
180
views
Have you come across this kind of "degree" concept?
Let $A \subseteq V(G)$ be a set of vertices in a graph $G$ and let $v \in V(G)$ be some vertex. Define $d_{A}(v)$ as the number of neighbours of $v$ inside $A$.
Now suppose you have a graph whose ...
- 6,962
8
votes
1
answer
733
views
6-regular bipartite graphs with no 8-cycles
I'm looking for simple 6-regular bipartite graphs with no 8-cycles, as small as possible. It doesn't matter if there are 4-cycles or 6-cycles, provided there are no 8-cycles. Such graphs must exist ...
- 37.7k
6
votes
3
answers
443
views
Number of trees with the same matching number
Let $\sigma(n,m)$ be the number of trees with $n$ vertices $\{ v_1, \dots, v_n \}$ such that the matching number (the size of a maximum matching) is $m$.
I have been trying to compute the value of $\...
- 201
8
votes
1
answer
328
views
Maximal class of simple graphs of order $n$ with mutually distinct numbers of spanning trees
This problem in some ways related to this post.
Let $A_n$ be the set of all integers $x$ such that there exist a connected simple graph of order $n$ having precisely $x$ spanning trees. Study the ...
- 3,463
2
votes
1
answer
250
views
Is there a polynomial upper bound for number of holes over following class of graphs?
A hole is chordless cycle that length of the cycle is four or more.
In this post I asked: What is the maximum number of holes that a simple graph on n vertices can have?
Gil Kalai answered that ...
- 519
2
votes
1
answer
291
views
Help on the following extremal problem?
An induced cycle is a cycle that is an induced subgraph of G; induced cycles are also called chordless cycles or (when the length of the cycle is four or more) holes.
Can anyone please tell me what ...
- 519
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.
...
- 37.7k
1
vote
0
answers
324
views
graphs with maximal number of paths of given length
Hi,
For a given number of edges, the non directed graph which maximises the number of paths of length 2 is the quasi-star or the quasi-complete graph.
Does anyone know :
1- what is the non directed ...
- 11
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
3
votes
1
answer
334
views
Degree conditions for k-factor
I am looking for a simple degree conditon that ensures the existence of a k-factor in a graph. The k is supposed to be relatively high and I don't mind the condition being a bit strict. Ideally, ...
- 6,962
4
votes
3
answers
241
views
Almost all graphs have a subgraph from a large class of graphs with constant order
I will pose the question in relation to trees but the more general question that can be deduced from the title of this post is also very interesting.
I suspect the question might have a very trivial ...
- 3,463
13
votes
1
answer
544
views
Induced Paths of Order 4
In a graph $G=(V,E)$ of order $n$, what fraction of the $\binom{n}{4}$ $4$-subsets of $V$ can induce the path of order four?
I looked at this question 30 years ago and was never able to come up with ...
user22090
8
votes
1
answer
587
views
What is the correct statement of this Erdös-Gallai-Tuza problem generalizing Turan's triangle theorem?
In Zsolt Tuza's Unsolved combinatorial problems I, Problem 46 is the following conjecture:
Let $G$ be a graph on $n$ vertices. Let $\alpha_1$ be the maximum number of edges of $G$ such that every ...
- 33.8k
2
votes
3
answers
708
views
Non-isomorphic graphs with the same numbers of closed walks
Can somebody help me to construct two family of finite simple connected graph $G_i$ and $H_i$, $i=1, 2, \cdots,n$ ($n$ possibly large), such that:
$1)$ $G_i\ncong H_i$ for $i=1, 2, \cdots, n$
$2)$ $...
- 4,784
4
votes
0
answers
434
views
Smallest matrix covered by many random n by n matrices
We say that a matrix $M$ can be covered by a (smaller) matrix $N$ if every entry in $M$ is contained in some submatrix of $M$ that exactly equals to $N$, up to reordering the rows and columns of $N$. ...
- 51
3
votes
1
answer
2k
views
If many triangles share edges, then some edge is shared by many triangles
Let $G=(V,E)$ be a graph.
Let $t$ denote the number of triangles in the graph, and $x$ denote the number of pairs of distinct triangles that share an edge.
(For example in $K_4$ we have $t=4$ and $x=6$...
- 337
9
votes
3
answers
983
views
Number of Geodesic Paths Passing Through a Vertex in an Expander Graph
Let $\{G_{n}\}$ be a sequence of $k$-regular expander graphs. For each $n$ assume that each pair of nodes in the graph is transmitting a unit load of traffic and the traffic goes through the minimum ...
- 3,626
9
votes
1
answer
579
views
What is the state of the art for the Turán number of $K_{4,4}$?
In Chung and Graham's "Erdős on Graphs: His legacy of unsolved problems," they discuss several open problems concerning Turán numbers for bipartite graphs.
There is a construction which gives graphs ...
- 7,857
2
votes
0
answers
148
views
Smallest size for an incomplete tournament with property $S_k$
By a well-known probabilistic argument due to Erdos, if $k>1$ is an integer then for all large enough $n$, there an asymmetric relation $R$ on $X=\lbrace 1,2, \ldots ,n \rbrace$ (i.e. $R \subseteq ...
- 3,595
5
votes
1
answer
830
views
Connected components of large induced subgraphs of hypercubes
Let $H$ be the $n$-dimensional hypercube, i.e. $\{0,1\}^n$ with edges between two vertices if and only if they differ in exactly one co-ordinate. We say that an edge is in direction $i$ if its ...
5
votes
1
answer
1k
views
Characterization of infinite paths in graphs
First an introduction.
A directed graph we all know what is, and a graph is serial whenever
every vertex has a successor. I do not consider the empty graph. A
pair $(\mathcal{G},s)$ is called a ...
- 126
9
votes
0
answers
441
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 ...
- 2,966
7
votes
1
answer
559
views
Graphs with many triangles but few complete graphs on 4 vertices
Let $G$ be a graph on $n$ vertices with $an^2$ edges containing at most $an^2/2$ copies of $K_4$. If there are cubically many triangles, say $cn^3$, then there is at least one edge that is not ...
- 2,966
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 $...
- 1,359
4
votes
1
answer
887
views
Existence of triangle-free graphs for regular graphs of degree at most n/2
It is known that for triangle-free graphs, if they are $d$-regular, then $2d\leq n$, where $n$ is the number of vertices. In words, the degree is less than or equal to half the number of vertices (...
- 43
1
vote
1
answer
319
views
Graphs far from being a collection of bicliques
A biclique is a complete bipartite graph. A graph is a "biclique collection" if it can be decomposed into the disjoint union of bicliques. Denote the set of such graphs by $\mathcal{BCC}$.
Given a ...
- 375
6
votes
3
answers
1k
views
Online Library of Unlabeled Connected Graphs on n Vertices
Does anyone know of the link to an online library of of unlabeled, connected graphs on n vertices? I remember looking at such an archive a few years ago while at a Macaulay 2 workshop, but I've been ...
- 1,324
6
votes
0
answers
889
views
Cliques of hyperedges
Suppose we have a graph, with multiple edges allowed. An edge-clique is a set $C$ of edges so that every two edges in $C$ share at least one endpoint. Note that any edge-clique falls into one of two ...
- 1,288
1
vote
2
answers
623
views
Bounds on the independence number of a graph
If $G$ is a graph with $n$ vertices and $\frac{nk}{2}$ edges, $k\ge -1,$ then $a(G)\ge \frac{n}{k+1}$. Why?
(Here $a(G)$ is the independence number).
- 11
7
votes
2
answers
756
views
Is the feedback vertex number bounded by the maximum number of leaves in a spanning tree?
I have a graph-theoretical conjecture which I think would have been studied before, but for which I cannot find anything in the literature.
Let G be a finite, simple, connected graph. Let the ...
- 495