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.

Filter by
Sorted by
Tagged with
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
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
16 votes
1 answer
585 views

Spanning trees: the last darn $1/4$

Let $\Gamma$ be a connected graph. By (Kleitman-West, 1991), if every vertex of $\Gamma$ has degree $\geq 3$, then $\Gamma$ has a spanning tree with $\geq n/4+2$ leaves, where $n$ is the number of ...
H A Helfgott's user avatar
  • 19.3k
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/...
user avatar
13 votes
0 answers
698 views

Is there a weak strong regularity lemma?

A famous strengthening of Szemerédi's regularity lemma, due to Alon, Fischer, Krivelevich and Szegedy, allows one to partition a graph into a bounded number of pieces in such a way that not only are ...
gowers's user avatar
  • 28.7k
12 votes
1 answer
829 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 ≥ ...
Robin Saunders's user avatar
6 votes
3 answers
429 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 $\...
Patt Geffrey's user avatar
5 votes
3 answers
1k views

Erdős–Stone theorem type edge density estimates for bipartite graphs?

The Erdős–Stone theorem theory says that the densest graph not containing a graph H (which has chromatic number r) has number of edges equal to $(r-2)/(r-1) {n \choose 2}$ asymptotically. However, ...
Rune's user avatar
  • 2,386
4 votes
0 answers
101 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: \...
H A Helfgott's user avatar
  • 19.3k
4 votes
1 answer
814 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 (...
Gizem's user avatar
  • 43
4 votes
1 answer
924 views

What is the minimum number of independent sets for a graph with fixed numbers of vertices and edges?

Fix integers $V$ and $E_{\text{max}}$, and consider graphs $G$ with $V$ vertices and at most $E_{\text{max}}$ edges. What is the best lower bound that one can give on the number of distinct ...
blt's user avatar
  • 1,203
4 votes
1 answer
170 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$, ...
Daniel Soudry's user avatar
4 votes
0 answers
244 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$ ...
Yonathan Touati's user avatar
3 votes
1 answer
124 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 ...
Lorenzo Pompili's user avatar
2 votes
3 answers
658 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)$ $...
Shahrooz's user avatar
  • 4,746
2 votes
0 answers
133 views

Even cycle constrained edge coloring

Is minimum colors needed to assign colors to edges of complete graph $K_n$ so that every $2t$ simple cycle where $t\in\Big\{1,\dots,2\Big\lfloor\frac{n}2\Big\rfloor\Big\}$ contains atleast $t+1$ ...
Turbo's user avatar
  • 13.7k
2 votes
2 answers
2k views

Maximum number of edges in bipartite graph without cycles of length 4

Let $ex(n,H)$ denote the maximum number of edges of a graph on $n$ vertices not containing a copy of $H$. Let $ex(n,m,H)$ denote the maximum number of edges of a bipartite graph with parts' sizes $m$ ...
Ilya's user avatar
  • 251
1 vote
1 answer
131 views

Connected sets with a large boundary in a privileged set

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: \...
H A Helfgott's user avatar
  • 19.3k
0 votes
1 answer
299 views

Looking for source: Max num of edges of graph with given number of vertices and given girth

In a paper I am reading, the author states: "It is simple and well known that a graph of girth $g$ and $q$ vertices has at most $q^{1+(O(1)/g)}$ edges" He says that a proof can be found on Extremal ...
josinalvo's user avatar
  • 193
0 votes
1 answer
115 views

Matching book embedding of Cartesian products of graphs

In the book embedding of a graph $G$ , each vertex of $G$ is placed on the spine and each edge is placed in the pages without crossing each other edge. If vertices have degree at most one in each ...
Jacob.Z.Lee's user avatar