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.
20
questions
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$, ...
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 ...
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 ...
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/...
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 ...
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 ≥ ...
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 $\...
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, ...
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: \...
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 (...
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 ...
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$, ...
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$ ...
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 ...
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)$ $...
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$ ...
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$ ...
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: \...
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 ...
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 ...