The extremal-graph-theory tag has no wiki summary.

**6**

votes

**1**answer

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

**25**

votes

**3**answers

570 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

**0**answers

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

**8**

votes

**1**answer

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

**5**

votes

**1**answer

150 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

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

**4**

votes

**1**answer

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

**7**

votes

**4**answers

307 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

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

**15**

votes

**1**answer

563 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

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

**11**

votes

**2**answers

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

**5**

votes

**1**answer

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

**0**

votes

**1**answer

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

**2**

votes

**0**answers

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

**5**

votes

**1**answer

284 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

430 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

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

**1**

vote

**0**answers

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

**5**

votes

**1**answer

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

**4**

votes

**1**answer

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

**2**

votes

**2**answers

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

**3**

votes

**1**answer

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

**1**

vote

**1**answer

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

**2**

votes

**2**answers

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

**1**

vote

**1**answer

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

**7**

votes

**1**answer

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

**5**

votes

**2**answers

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

**8**

votes

**1**answer

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

**0**

votes

**1**answer

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

**0**

votes

**1**answer

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

**14**

votes

**2**answers

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

**1**

vote

**0**answers

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

**15**

votes

**2**answers

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

**3**

votes

**1**answer

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

**4**

votes

**3**answers

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

**12**

votes

**1**answer

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

**6**

votes

**0**answers

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

**2**

votes

**3**answers

471 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**

votes

**0**answers

408 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$. ...

**1**

vote

**1**answer

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

**9**

votes

**2**answers

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

**8**

votes

**1**answer

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

**2**

votes

**0**answers

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

**5**

votes

**1**answer

550 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

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

**4**

votes

**0**answers

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

**7**

votes

**1**answer

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

**21**

votes

**4**answers

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

**2**

votes

**1**answer

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