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
4
votes
1
answer
183
views
Minimal size of the maximal biclique
We examine a bipartite graph with two sides $R$ and $L$, and denote by $|L|$ and $|R|$ the number of nodes in each side. We know only that each node on side $R$ is connected to $k$ nodes on side $L$, ...
- 968
4
votes
1
answer
1k
views
What is the minimum diameter of $r$-regular, $k$-connected graphs?
Let $md_r^k(n)$ be the minimum diameter over all $r$-regular, $k$-connected graphs on at least $n$ vertices. (Let us assume $r, k \geq 2$).
Problem: Find lower and upper asymptotic bounds on $md_r^...
- 399
4
votes
0
answers
160
views
"Neighborhood-Bounded" regular graphs
Lately I have been interested in questions surrounding strongly regular graphs, and came across this question that I have been struggling to make progress on. (For the sake of being explicit, a graph $...
- 51
4
votes
0
answers
113
views
What properties do graphs avoiding large regular subgraphs have?
Fix a positive integer $r$ and real $\delta \in (0,1)$.
Let $G$ be an undirected graph on $n$ vertices. Suppose that $G$ does not contain an $r$-regular subgraph on at least $\delta n$ vertices (i.e., ...
- 557
4
votes
0
answers
241
views
Weight transfer proof of Turán’s theorem
Turán’s theorem, which states that a $K_{p+1}$-free graph contains at most $(1-1/p)\frac{N^2}{2}$ edges, can be proven in many different ways, as pointed out, for example in M. Aigner, G. M. Ziegler, ...
4
votes
1
answer
465
views
Turán's theorem for cosets of groups
Let $G$ be a finite group, $G',H$ be its subgroups and $H'=G'\cap H$. For each $g\in G$, we create a map $f_g:G'/H'\rightarrow G/H: aH'\rightarrow gaH$. It's easy to see that the map is well defined ...
- 1,462
4
votes
0
answers
102
views
Connected sets with large boundary in a multigraph
Let $G=(V,E)$ be a connected, undirected graph. Define the boundary $\partial S$ of a set $S\subset V$ to be the set of all $v\notin S$ joined to $S$ by an edge, i.e.
$$\partial S = \{v\not \in S: \...
- 20.2k
4
votes
0
answers
257
views
Graphs with high girth and low diameter
As the title says, I'm interested in graphs with high girth and low diameter.
Given a class $\Gamma$ of finite $k$-regular graphs, call a $\Gamma$-graph GD-extremal if every $\Gamma$-graph either has ...
- 3,612
4
votes
0
answers
104
views
Maximal number of smallest circuits in a matroid
It is known (see here for example) that, in a simple graph of odd genus $g$ with $n$ vertices and $m$ edges, the number of cycles of lenght $g$ is at most $\frac{n(m-n+1)}{g}$.
Since this can be be ...
- 3,446
4
votes
0
answers
82
views
Expected number of bridges in a random subgraph
I am researching connectivity in random subgraphs and have come across the following problem.
A bridge between two vertices $a$ and $b$ of a graph $G$ is an edge $e$ such that removing $e$ from $G$ ...
- 175
4
votes
0
answers
145
views
Can the vertices of a planar graph of min degree 3 be covered with edges of average weight ( sum of degrees) at most 14?
Consider a planar graph where every vertex is incident to at least 3 edges, and assign to each edge a weight equal to the sum of the degrees of its endpoints.
If not, what is the smallest n so that ...
- 111
4
votes
0
answers
116
views
Faithful Orthogonality Dimension of Kneser Graphs
Let us consider the complement of the Kneser graph with parameters $n$ and $n/4$. The vertex set of our graph $K$ is the set $\binom{[n]}{n/4}$ of $n/4$-subsets of $[n]$, and two vertices are joined ...
- 211
4
votes
0
answers
251
views
Blocking directed paths on a DAG with a linear number of vertex defects
Let $G=(V,E)$ be a directed acyclic graph.
Define the set of all directed paths in $G$ by $\Gamma$.
Given a subset $W\subseteq V$, let
$\Gamma_W\subseteq \Gamma$ be the set of all paths in $\Gamma$ ...
- 141
4
votes
0
answers
143
views
Halin Graphs with Highest Number of Hamilton Cycles
Halin graphs contain a Hamilton cycle and have the interesting property, that, also in the case of arbitrary real edge weights, it is possible to report one of the shortest contained Hamilton cycles ...
- 13.2k
4
votes
0
answers
125
views
Percolation in torus under threshold rule
As part of my graduate research I am currently studying the last section in the paper "Random Majority Percolation" by Balister, Bollobas et al. The paper itself is very complicated but the last two ...
- 41
4
votes
0
answers
46
views
Two possible generalizations of a theorem of Kotlov about the Hamming Cube
The following theorem is proved here
Let $Q_n=(V,E)$ be the Hamming graph, and let $S \subseteq V$, $|S|<2^{n-1}$. Then the induced subgraph on $V \setminus S$, $Q_n[V \setminus S]$, has a ...
- 736
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
3
votes
1
answer
766
views
Smallest triangle-free graph with chromatic number 5
The Grötzsch graph is triangle-free and has chromatic number 4. At 11 vertices it is the (unique) smallest graph with these properties.
What is the smallest number of vertices needed for a triangle-...
- 9,114
3
votes
1
answer
155
views
Does Sidorenko's conjecture hold when the host graph's maxdegree/mindegree is a constant?
Does the following holds?
For every bipartite graph $H$ and every graph $G$ with $\frac{\Delta(G)}{\delta(G)}\leq 2$,
$$t(H,G)\geq t(K_2, G)^{e(H)}.$$
If not sure, is this a equal question as ...
- 359
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
3
votes
2
answers
859
views
Complete k-partite graph covers all K_k of a graph
Suppose that we have a complete graph $G$ of $n$ vertices. What is the minimum number of complete $k$-partite graph (subgraph of $G$) that covers all the complete graph of $k$ vertices of $V(G)$? Are ...
- 356
3
votes
2
answers
276
views
Ramsey-Turán density function is well defined
Define
$$RT(n,K_l,f(n))=ex_l(n,f(n))=\max_G\{e(G): K_l \not\subset G, v(G)=n, \alpha(G)\leq f(n)\}$$
and the Ramsey-Turán density function $f_l:(0,1] \to \mathbb{R}$ as
$$f_l(\alpha)=\lim_{n\to \infty}...
- 227
3
votes
1
answer
158
views
Sharp upper bound of the number of edges for graphs of thickness two
A graph $G=(V,E)$ has thickness $2$ if $E$ can be written as a disjoint union $E=E_1\cup E_2$ so that $G_1:=(V,E_1),G_2:=(V,E_2)$ are planar graphs. For instance, $K_5$ has thickness $2$. It is known ...
- 1,075
3
votes
1
answer
175
views
Minimum size of regular graph with no short cycles
For $d \geq 3$ (degree) and $r \geq 3$ (radius), say that a $d$-regular (finite, simple, non-oriented) graph $G$ is $r$-almost-tree if it contains no cycle of length $\leq 2 r$: in other words, we ...
- 284
3
votes
1
answer
305
views
Counting the forests obtainable by removing subtrees from binary trees
Let $B_h$ be the perfect binary tree having height $h$ (i.e. the binary tree with height $h$ in which all interior nodes have two children and all leaves have the same depth or same level).
For any ...
- 1,677
3
votes
1
answer
204
views
How many graphs of order n, maximum degree k, and maximum diameter d exist?
The total number of simple undirected graphs of order $n$ is
$\sum\limits_{i = 0}^{\frac{n(n-1)}{2}}{\binom{\frac{n(n-1)}{2}}{i}} = 2^{\frac{n(n-1)}{2}}$.
What is the number of simple undirected ...
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
3
votes
1
answer
81
views
Can we say a partial order set is 2-dimensional if its comparability graph does not contain an asteroidal triple?
I think it is true that if the comparability graph of a poset contains an asteroidal triple then it is at-least 3 dimensional. I want to know if the converse is true, i.e. if there exists no ...
3
votes
1
answer
289
views
Graph properties that imply a bounded number of edges
Many combinatorial problems can be reduced to bounding the number of edges in a given graph with $n$ vertices. Each time I encounter such a problem, I check whether the corresponding graph has a ...
- 1,072
3
votes
2
answers
100
views
Maximum density of a double-node-colored graph
Let $G$ be a graph with the following properties. $C$ is a set of colors. The nodes of $G$ are $C \choose 2$. For any node $v$, the neighborhood of $v$ is rainbow -- that is, for any two nodes $x, ...
- 1,389
3
votes
1
answer
139
views
Turán density of an unbalanced complete $r$-partite $r$-graph
In a survey by Füredi and Simonovits called "The history of degenerate (bipartite) extremal graph problems," Theorem 10.5 states the following:
Let $\mathcal K = K^{(r)}(a_1, \dots, a_r)$ ...
- 131
3
votes
1
answer
121
views
The least number of edges to add to a tree that would force a certain number of edge-disjoint cycles
Let $c(n,k)$ be the least integer such that if $G$ is a simple graph on $n$ vertices with $n + c(n,k) - 1$ edges then $G$ has $k$ edge-disjoint cycles.
Clearly, $c(n, 1) = 1$ and it not very hard to ...
- 1,034
3
votes
1
answer
179
views
Reference Request: designing a tree of "main roads" in a graph
Let $G = (V, E)$ be an undirected finite connected graph. Let $u$ be a specified vertex of $G$. Then the sum of distances
$$
\sum_{v \in V} d_G(u,v)
$$
is defined. Now we want to decrease this value, ...
- 1,551
3
votes
0
answers
108
views
Harper's theorem on the general Hamming graph
Let $G$ be a graph, and for every $S \subseteq V$, let $N(S)$ denote the neighborhood of $S$ (i.e., the set of vertices that have neighbors in $S$). The vertex expansion of $G$ is
$$ \min_{S\subseteq ...
- 419
3
votes
0
answers
331
views
Behrend's construction vs. Triangle removal lemma
I was reading Zhao's book "Graph theory and additive combinatorics" and on page 71 I came across Remark 2.5.4 which I'd like to understand.
Theorem 2.3.1 (Triangle removal lemma) For all $\...
- 330
3
votes
0
answers
93
views
Connected set of vertices having large boundary in a subset?
Let $\Gamma = (V,E)$ be a connected (undirected) graph where every vertex has degree $\geq 2$. Let $E'\supset E$ be a larger set of edges between elements of $V$ such that every vertex of $\Gamma'=(V,...
- 20.2k
3
votes
0
answers
70
views
Boundary differences in two graphs
Let $\Gamma, \Xi$ be two graphs with the same set of vertices $V$ with $n$ elements. Assume $\Gamma$ is connected. Write $\Gamma\cup \Xi$ (or $\Gamma\cap \Xi$) for the graph whose set of edges is the ...
- 20.2k
3
votes
0
answers
94
views
The pagenumber of subdivision of a complete graph
A book embedding of a graph $G$ consists of placing the vertices of $G$ on a spine and assigning edges of the graph to pages so that edges in the same page do not cross each other. The book thickness $...
- 767
3
votes
0
answers
66
views
An extremal problem in directed path systems
The following is a common rephrasing of the well-known open problem in extremal graph theory to (asymptotically) determine $ex(n, C_8)$:
What is the asymptotically maximum $L = L(n)$ such that ...
- 1,389
3
votes
0
answers
97
views
What is the number of independent sets in graph of this type?
Suppose we have a graph $G(V,E)$
What is the number of independent sets in graph of this type?
I have an idea to use reccurence
$$|G|=|G\backslash \{v\}|+|G\backslash n(v)|$$
where $|G|$ is the ...
2
votes
1
answer
2k
views
The maximum number of edges in an even-cycle-free graph with $n$ vertices
Problem
Given any positive integer $n$, what is the maximum number of edges in an even-cycle-free graph with $n$ vertices?
Is the above problem an unsolved problem in extremal graph theory? Are there ...
- 1,997
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
2
votes
1
answer
482
views
Suppose the independent number of a graph is bounded. How small the clique number can be?
Suppose the independent number of a graph is bounded. How small the clique number can be? linear?
It seems to be a natural problem to ask. but I could not find any reference.
Thanks.
- 23
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
2
votes
2
answers
721
views
Minimal Non-planar Extensions of a Graph
Given a planar graph $G=(V,E)$ with vertices $V$ and edges $E$, call $\bar G = (V,\bar E)$ a non-planar extension of $G$ if $\bar G$ is non-planar and $E \subset \bar E$.
I'm interested in minimal ...
- 543
2
votes
1
answer
407
views
On the maximum number of $t$-subset of $\{1,\ldots, n\}$ having pairwise singleton or empty intersections
Let $n$, $t \in \mathbb N$ two natural numbers such that $0<t<n$, and let $A$ be a set of $n$ elements.
We call a quasi-partition or q-p of $A$ a subset $W \subset \mathcal P(A)$ such that we ...
- 307
2
votes
2
answers
143
views
Regarding a specific Turán number of graphs
I wish to know the latest bound on the number of edges a graph of girth greater than or equal to $t$ can have.
Specifically, I heard somewhere that a graph of girth greater than or equal to $t$ can ...
- 2,089
2
votes
1
answer
131
views
Turán density of hypergraphs with very few edges
As usual, for an $r$-uniform hypergraph $G$, denote by $ex_r(n,G)$ the maximum number of edges an $r$-uniform, $G$-free hypergraph on $n$ vertices can have, and let $\lim \frac{ex_r(n,G)}{\binom nr}\...
- 19.1k
2
votes
1
answer
239
views
Subsets of a graph, maximal w.r.t. the property of inducing a subgraph with minimum degree at least $k$
Let $G=(V,E)$ be a simple undirected graph. Define an mmd$k$s in $G$ (for 'maximal minimum degree $k$ subset') to be any subset $S$ of $V$ such that
the subgraph induced by $S$ in $G$ has minimum ...
- 393