Skip to main content

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
9 votes
0 answers
442 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
398 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
134 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
78 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
131 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, ...
8 votes
2 answers
615 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 ...
5 votes
2 answers
516 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|} \right\}.$$...
0 votes
1 answer
814 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 ...
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 ...
-1 votes
1 answer
199 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 ...
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$...
6 votes
2 answers
863 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 ...
8 votes
1 answer
338 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
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 ...
8 votes
1 answer
587 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 ...
25 votes
3 answers
1k 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 ...
9 votes
1 answer
1k 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 non-...
6 votes
0 answers
315 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 ...
10 votes
1 answer
333 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 ...
7 votes
4 answers
950 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 ...
6 votes
1 answer
243 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: Dirac-...
13 votes
2 answers
870 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
437 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
582 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 ...
6 votes
1 answer
796 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 ...
11 votes
0 answers
310 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 $\Theta((4/3)^n/...
2 votes
0 answers
285 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
175 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 $...
4 votes
1 answer
1k 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 $2^{(1-...
8 votes
1 answer
328 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
1k 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, ...
1 vote
1 answer
180 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 ...
2 votes
1 answer
250 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 ...
1 vote
0 answers
324 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 ...
4 votes
3 answers
241 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 ...
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, ...
13 votes
1 answer
544 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 ...
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 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$. ...
9 votes
1 answer
579 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
148 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
830 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
1k 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 ...
7 votes
1 answer
560 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
1k 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 $...
1 vote
1 answer
319 views

Graphs far from being a collection of bicliques

A biclique is a complete bipartite graph. A graph is a "biclique collection" if it can be decomposed into the disjoint union of bicliques. Denote the set of such graphs by $\mathcal{BCC}$. Given a ...
6 votes
3 answers
1k views

Online Library of Unlabeled Connected Graphs on n Vertices

Does anyone know of the link to an online library of of unlabeled, connected graphs on n vertices? I remember looking at such an archive a few years ago while at a Macaulay 2 workshop, but I've been ...
6 votes
0 answers
889 views

Cliques of hyperedges

Suppose we have a graph, with multiple edges allowed. An edge-clique is a set $C$ of edges so that every two edges in $C$ share at least one endpoint. Note that any edge-clique falls into one of two ...
1 vote
2 answers
623 views

Bounds on the independence number of a graph

If $G$ is a graph with $n$ vertices and $\frac{nk}{2}$ edges, $k\ge -1,$ then $a(G)\ge \frac{n}{k+1}$. Why? (Here $a(G)$ is the independence number).
7 votes
2 answers
756 views

Is the feedback vertex number bounded by the maximum number of leaves in a spanning tree?

I have a graph-theoretical conjecture which I think would have been studied before, but for which I cannot find anything in the literature. Let G be a finite, simple, connected graph. Let the ...