The extremal-graph-theory tag has no usage guidance.

**0**

votes

**1**answer

226 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 ...

**6**

votes

**1**answer

385 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 ≥ ...

**-1**

votes

**0**answers

81 views

### $(r+1)$ Clique of a Induced Subgraph ensured by Edge Number of the Graph

$G$ is a $s$ regular graph.
$E$ is the number of edges of $G$.
$n$ is the total number of vertices of $G$.
$A$ is a set of $t$ vertices where $|A| = t;0<t<n$ and $A \subseteq G$.
Problem: ...

**16**

votes

**2**answers

869 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.
...

**6**

votes

**2**answers

251 views

### extremal bipartite graph

I'm facing the following question:
Given a bipartite graph $G = (L \cup R, E)$.
Let $n = |L|$, $m = |R|$, and a parameter $k \in \mathbb{N}$, $n > m > k$.
What is a minimal possible number ...

**2**

votes

**0**answers

188 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 ...

**8**

votes

**0**answers

361 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 ...

**0**

votes

**1**answer

85 views

### Forbidden Tripartite Graphs

I was looking at extremal graph theory. I have understood the proofs of upper bounds for the Zarankiewicz problem which basically states: What can you say about the edges of a graph with $n$ vertices ...

**2**

votes

**0**answers

63 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

**0**answers

46 views

### Maximum cardinality general factor of a graph

Given a graph $G=(V,E)$ and a set of integers $B(v)$ associated to each vertex, a general factor of $G$ is a set of edges $F\subseteq E$ such that the degree of each vertex $v\in V$ in the graph $(V, ...

**1**

vote

**0**answers

114 views

### What are constructions for induced $C_5$-free graphs?

During a recent workshop, the question came up whether there are some constructions for graphs that are induced $C_5$-free, but they contain "everything else," so we don't want to forbid $C_5$'s, ...

**7**

votes

**2**answers

417 views

### Embedding of planar graphs

I've recently come across the following lemma.
Lemma (Valiant): A planar graph $G$ with maximum degree $4$ can be embedded in the plane using $O(|V|)$ area in such a way that its vertices are at ...

**4**

votes

**2**answers

183 views

### Vertex expansion of the Hamming graph

Let $G$ be a graph, and for every $S \subseteq V$, let $N(S)$ denote the neighborhood of $S$. The vertex expansion of $G$ is
$$ \min_{S\subseteq V, |S|\le |V|/2} \left\{ \frac{|N(S)|}{|S|} ...

**4**

votes

**2**answers

345 views

### How many simple cycles can a graph with $n$ vertices and $m$ edges have?

I am mainly interested in the smallest number of simple cycles a graph with $n$ vertices and $m$ edges must have.
For example, if $m\le n-1$, this number is $0$, then if $n\le m \le 3(n-1)/2$, it is ...

**0**

votes

**1**answer

169 views

### Edge-disjoint cycles in graphs

Given a graph $G=(V,E)$ and a fixed integer $k$ are there any algorithms known which would find the maximum number of edge-disjoint cycles of length $k$ in $G$? If not is there a proof that this ...

**2**

votes

**2**answers

214 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 ...

**-1**

votes

**1**answer

64 views

### Maximum degree and matching number

Let $G=(V,E)$ be a finite graph. We write $\nu(G)$ for the matching number of $G$. Is there $\varepsilon > 0$ such that we have $$\frac{\nu(G)+\Delta(G)}{V(G)} \geq \varepsilon$$ for all finite ...

**2**

votes

**1**answer

622 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 ...

**6**

votes

**2**answers

446 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 ...

**11**

votes

**1**answer

647 views

### Cauchy-Schwarz proof of Sidorenko for 3-edge path (Blakley-Roy inequality)

Is there a "Cauchy-Schwarz proof" of the following inequality?
Theorem. Given $f \colon [0,1]^2 \to [0,1]$, one has
$$
\int_{[0,1]^4} f(x,y)f(z,y)f(z,w) \, dxdydzdw \geq \left(\int_{[0,1]^2} f(x,y) ...

**8**

votes

**1**answer

222 views

### Spectral lower bounds on the diameter of a graph

There is such a bound, due to Mohar and McKay, using the second-smallest eigenvalue of the Laplacian $\lambda_{2}$:
$$Diam \geq \lceil \frac{4}{n\lambda_{2}} \rceil.$$
This bound is very elegant but ...

**2**

votes

**1**answer

236 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 ...

**8**

votes

**1**answer

424 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 ...

**24**

votes

**3**answers

720 views

### Removal of non-isomorphic edges results in the same graph

There exists a (simple unlabeled) graph on 6 nodes with a pair of non-isomorphic edges (i.e., there is no graph automorphism that sends one edge into the other) such that removal of either of them ...

**7**

votes

**1**answer

322 views

### Smallest Connected Graph for Given Degree Sequence

For a given integer sequence $(d_1, d_2,...,d_n)$, a natural question is if such a sequence is graphical, i.e. is a degree sequence of some graph. According to Erdős–Gallai theorem, A sequence of ...

**7**

votes

**0**answers

228 views

### Algorithms for computing the Resilience of Graphs

The definition of resilience with a graph $G$ w.r.t to a monotone property $\mathcal{P}$ is well known.
(Global resilience) Let $\mathcal{P}$ be an increasing monotone property. The global ...

**4**

votes

**1**answer

231 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 ...

**6**

votes

**1**answer

194 views

### Can I weaken the minimum degree hypothesis in Nash-Williams' triangle decomposition conjecture?

In what follows, all graphs $G$ are $K_3$-divisible (all degrees even, number of edges a multiple of three) on $n$ vertices, where $n$ is not too small.
The famous Nash-Williams conjecture claims ...

**8**

votes

**5**answers

1k 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 ...

**7**

votes

**4**answers

365 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 ...

**2**

votes

**1**answer

118 views

### Point-Hyperplane incidence in finite projective spaces

Let $P$ be a finite projective space of order $q$ and dimension $d$. I am interested in finding the least $k$ such that for any set $S$ of $k$ points of $P$, and for any set $S'$ of $k$ hyperplanes of ...

**16**

votes

**1**answer

799 views

### Paul Erdős: 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".
...

**6**

votes

**1**answer

142 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:
...

**5**

votes

**2**answers

263 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 ...

**11**

votes

**2**answers

456 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 ...

**4**

votes

**1**answer

292 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 ...

**6**

votes

**1**answer

380 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 ...

**5**

votes

**1**answer

518 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 ...

**8**

votes

**0**answers

187 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 ...

**2**

votes

**1**answer

383 views

### existence of triangle-free graphs for sparse 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 the half of the number of ...

**2**

votes

**0**answers

123 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 ...

**1**

vote

**1**answer

117 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 ...

**3**

votes

**1**answer

351 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 ...

**8**

votes

**1**answer

280 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 ...

**2**

votes

**2**answers

323 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, ...

**7**

votes

**1**answer

505 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 ...

**2**

votes

**2**answers

383 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 ...

**15**

votes

**2**answers

820 views

### Minimal graphs with a prescribed number of spanning trees

As its 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 ...

**1**

vote

**1**answer

165 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 ...

**9**

votes

**2**answers

705 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 ...