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

**2**

votes

**1**answer

78 views

### How many graphs of order n, maximum degree k, and maximum diameter d exist?

The total number of simple undirected graphs of order $n$ is
$\sum\limits_{i = 0}^{\frac{n(n-1)}{2}}{\binom{\frac{n(n-1)}{2}}{i}} = 2^{\frac{n(n-1)}{2}}$.
What is the number of simple undirected ...

**5**

votes

**1**answer

104 views

### Length minimizing graphs between a finite set of points

Consider a set of $n$ points in the plane. Among all the connected graphs (trees) $T$ in the plane that have these $n$ points among their vertices, I am looking to find one such that the sum of its ...

**-1**

votes

**1**answer

76 views

### Existence of a graph with strong restrictions

Given a maximal degree $k$ and maximal diameter $d$. We identify 3 nodes, $i$, $j$, and $v$. Can an undirected graph exist, such that:
all nodes but $v$ have full degree $k$ ($v$ having a lower ...

**8**

votes

**0**answers

117 views

### Minimal number of colours in distinguishing colouring of biconnected graphs

A colouring of edges of a graph is distingushing if no non-identity automorphism of the graph preserves this colouring.
Problem. Is it true that each biconnected graph possesses a distinguishing ...

**5**

votes

**1**answer

205 views

### Blocking $a\to b\to c$ in a DAG with bounded degrees

(This is an (easy-looking) toy question for this one.)
Question. Find the smallest $\alpha$ satisfying the following:
Let $G=(V,E)$ be a finite directed acyclic graph, where each in- and out-...

**1**

vote

**1**answer

42 views

### Lower bound construction for the extremal number of $C_{2k}$-free bipartite graph

Suppose $G(V_1 \cup V_2, E)$ is a bipartite graph with parts $|V_1|=n$ and $|V_2|=m.$ What is the best known lower bound construction for the maximum number of edges in $G$ when $G$ does not have a ...

**8**

votes

**1**answer

176 views

### Maximum number of triangles no two of which have a common edge

For $n\in N_+$, define f(n) to be that for any n-vertice graph G, if any two triangle in G don't have a common edge, then G has at most f(n) triangles.
Do we have some good estimates for f(n)?
By ...

**3**

votes

**0**answers

114 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

**0**answers

107 views

### Halin Graphs with Highest Number of Hamilton Cycles

Halin graphs contain a Hamilton cycle and have the interesting property, that, also in the case of arbitrary real edge weights, it is possible to report one of the shortest contained Hamilton cycles ...

**6**

votes

**0**answers

93 views

### What is the smallest number of vertices in a graph whose every orientation contains a directed straight path of length 3

For a graph $\Gamma$ and a digraph $\vec H$ we write $\Gamma\Rightarrow \vec H$ if any orientation of $\Gamma$ contains an isometric and isomorphic copy of the digraph $\vec H$. Since each graph ...

**1**

vote

**2**answers

138 views

### Extremal density of a graph without a non-backtracking $2k$-cycle

The current best bound for the maximum possible density of an $n$-node graph with girth (shortest cycle length) $>2k$ is of the form
$$ex(n \ \mid \ C_{\le 2k}) = O(n^{1 + 1/k}),$$
while the ...

**6**

votes

**3**answers

351 views

### Kovari-Sos-Turan theorem

Let $r \leq s$ be fixed natural numbers. Then by the Kővári–Sós–Turán theorem, any graph on $n$ vertices with at least $cn^{2-\frac{1}{r}}$ edges contains a complete bipartite subgraph $K_{r,s}$ for a ...

**3**

votes

**1**answer

209 views

### Smallest triangle-free graph with chromatic number 5

The Grötzsch graph is triangle-free and has chromatic number 4. At 11 vertices it is the (unique) smallest graph with these properties.
What is the smallest number of vertices needed for a triangle-...

**4**

votes

**0**answers

75 views

### Percolation in torus under threshold rule

As part of my graduate research I am currently studying the last section in the paper "Random Majority Percolation" by Balister, Bollobas et al. The paper itself is very complicated but the last two ...

**10**

votes

**0**answers

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

**4**

votes

**0**answers

35 views

### Two possible generalizations of a theorem of Kotlov about the Hamming Cube

The following theorem is proved here
Let $Q_n=(V,E)$ be the Hamming graph, and let $S \subseteq V$, $|S|<2^{n-1}$. Then the induced subgraph on $V \setminus S$, $Q_n[V \setminus S]$, has a ...

**7**

votes

**1**answer

232 views

### The maximal number of copies of a graph $T$ in an $H$-free graph

Problem. Let $T,H$ be fixed graphs with $H$ being a tree, not isomorphic to a subgraph of $T$. Let $ex(n,T,H)$ be the maximal number of copies of $T$ in an $H$-free graph on $n$ vertices. Is it always ...

**3**

votes

**1**answer

169 views

### Reference Request: designing a tree of “main roads” in a graph

Let $G = (V, E)$ be an undirected finite connected graph. Let $u$ be a specified vertex of $G$. Then the sum of distances
$$
\sum_{v \in V} d_G(u,v)
$$
is defined. Now we want to decrease this value, ...

**2**

votes

**0**answers

35 views

### Estimates for the drop in the sum of all pairwise weighted distances effected by a decrease of the weight of an edge

Consider simple connected undirected graphs $G = (V, E)$ equipped with a function $w\colon E\rightarrow \{x\in \mathbb{R}\colon x\geq 0\}$.
Define a function $d_{G,w}\colon V\times V\rightarrow\...

**2**

votes

**1**answer

102 views

### Subsets of a graph, maximal w.r.t. the property of inducing a subgraph with minimum degree at least $k$

Let $G=(V,E)$ be a simple undirected graph. Define an mmd$k$s in $G$ (for 'maximal minimum degree $k$ subset') to be any subset $S$ of $V$ such that
the subgraph induced by $S$ in $G$ has minimum ...

**2**

votes

**1**answer

125 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$, ...

**2**

votes

**0**answers

47 views

### An extremal problem in directed path systems

The following is a common rephrasing of the well-known open problem in extremal graph theory to (asymptotically) determine $ex(n, C_8)$:
What is the asymptotically maximum $L = L(n)$ such that ...

**3**

votes

**0**answers

90 views

### What is the number of independent sets in graph of this type?

Suppose we have a graph $G(V,E)$
What is the number of independent sets in graph of this type?
I have an idea to use reccurence
$$|G|=|G\backslash \{v\}|+|G\backslash n(v)|$$
where $|G|$ is the ...

**1**

vote

**0**answers

56 views

### Cut norm and biclique gap?

Given real $\pm1$ matrix $M\in\Bbb R^{n\times m}$ we have that cut-norm is given by $$\|M\|_C=\max_{\mathcal I\subseteq[n],\mathcal J\subseteq[m]}\Big|\sum_{(i,j)\in\mathcal I\times\mathcal J}M_{ij}\...

**2**

votes

**1**answer

407 views

### The maximum number of edges in an even-cycle-free graph with $n$ vertices

Problem
Given any positive integer $n$, what is the maximum number of edges in an even-cycle-free graph with $n$ vertices?
Is the above problem an unsolved problem in extremal graph theory? Are there ...

**3**

votes

**1**answer

167 views

### Graph properties that imply a bounded number of edges

Many combinatorial problems can be reduced to bounding the number of edges in a given graph with $n$ vertices. Each time I encounter such a problem, I check whether the corresponding graph has a ...

**-3**

votes

**2**answers

208 views

### Concepts of criticality in graph theory

A graph $G=(V,E)$ is said to be vertex-critical if removing a vertex $v\in V$ reduces the chromatic number $\chi(\cdot)$. Edge-criticality is defined in a similar manner. Moreover, $G$ is called ...

**3**

votes

**1**answer

201 views

### What is the minimum diameter of $r$-regular, $k$-connected graphs?

Let $md_r^k(n)$ be the minimum diameter over all $r$-regular, $k$-connected graphs on at least $n$ vertices. (Let us assume $r, k \geq 2$).
Problem: Find lower and upper asymptotic bounds on $md_r^...

**7**

votes

**1**answer

363 views

### Drawing trees on small number of lines in 2D and 3D

Problem. Given a tree do we need fewer lines in 3D than in 2D in order to draw it straightline and crossing-free?
(Asked 01.10.2016 by Alexander Wolff on page 20 of Volume 1 of the Lviv Scottish Book)...

**1**

vote

**0**answers

48 views

### Constructing graphs from subsets of a minimal alphabet

From an alphabet of $N$ letters, choose $n$ pairwise distinct subsets $ v_1,\dots,v_n$ of a fixed size $k$ and define a graph on $V=\{v_1,\dots,v_n\}$, which has an edge for each pair of vertices that ...

**4**

votes

**1**answer

79 views

### Maximal number of perfect matchings that pairwise form a Hamiltonian cycle

Definition: Let $MH(n)$ be the maximal number of perfect matchings (1-regular graphs) on $n$ vertices where the union of any two perfect matchings is a Hamiltonian cycle.
Question: Is it true that $...

**4**

votes

**0**answers

53 views

### Cage graphs and even cycles

Let $G$ be a $(\nu,g)$-cage graph of degree $\nu$ with girth $g$ and $n=n(\nu,g)$ vertices.
Based on the known examples, I am wondering if the following can be proved/disproved:
Is it true that ...

**0**

votes

**1**answer

106 views

### Intersection property of Szemerédi's regularity condition

We adopt common notations in the study of Szemerédi's regularity lemma and only focus on simple graph $G(V,E)$. For any two disjoint vertex sets $A,B\subset V$, we say the pair $(A,B)$ is $\varepsilon-...

**0**

votes

**0**answers

141 views

### A Non-trivial intersecting set system problem

Liven large enough $k\in\Bbb N$ fix $m\in\{2,3,\dots,k\}$ and fix $4k$ cardinality set $K_{4k}$.
What is the maximum $n\in\Bbb N$ such that at some $t\geq2n-1$ there are $$\mbox{ subsets }L_1,L_2,\...

**2**

votes

**0**answers

213 views

### possible degree sequences for a graph with multiple edges but no loops

Let $G$ be a graph on $n$ vertices. $G$ is allowed to have multiple edges but no loops. The degree sequence of $G$ is the tuple $(d_1,d_2,\ldots,d_n)$ with $d_1\geq d_2 \geq\cdots\geq d_n\geq 0$ ...

**2**

votes

**2**answers

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

**2**

votes

**1**answer

106 views

### Finite limit to the size of an intersecting family of k-sets with no smaller intersecting set?

Suppose we have a family $F$ such that:
For each $A \in F$ we have $|A| = k$
For each $A,B \in F$ we have $A \cap B \neq \emptyset$
If we have $C$ such that for each $A \in F$ we get $C \cap A \neq \...

**3**

votes

**2**answers

93 views

### Maximum density of a double-node-colored graph

Let $G$ be a graph with the following properties. $C$ is a set of colors. The nodes of $G$ are $C \choose 2$. For any node $v$, the neighborhood of $v$ is rainbow -- that is, for any two nodes $x, ...

**6**

votes

**0**answers

172 views

### The smallest order of a 4-chromatic graph of given girth

Let $n_4(g)$ denote the smallest order of a $4$-chromatic graph with girth $g$. It is known that $n_4(4)=11$ [2] and $n_4(5)=21$ [1]. By a famous proof of Erdös, it is known that $n_4(g)$ is well-...

**5**

votes

**1**answer

812 views

### Bounds for number of edges of a graph, given girth and number of vertices

In reading a paper, I came across an affirmation
"a graph of girth $g$ and $q$ vertices has at most $q^{1+(O(1)/g)}$ edges"
In a previous question I asked in this site about it, I was reffered to a ...

**0**

votes

**1**answer

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

**10**

votes

**0**answers

168 views

### Asymptotics of subgraph densities in graphons

In Pittel (1989)'s solution to a problem of Knuth (1976) on the expected number of stable matchings between $n$ men and $n$ women under uniform random preferences, it was shown that, as $n \to \infty$,...

**0**

votes

**0**answers

37 views

### Possible Number of Repetation of a Submatrix

Notation:
$H$ is the adjacency matrix of graph $H'$ respectively. $H_k$ is the block or sub-matrix of matrix $H$. The adjacency matrix of graph $H_k \cup H_e$ (subgraphs of $H'$) is $M_{(k,e)}$ ...

**0**

votes

**1**answer

151 views

### Reference for Turan Density

I am working a 3-graph problem. I convert it to calculate Turan density, that is $lim_{n\to \infty}\frac{ex_3(n,F)}{\binom{n}{3}}$, where F is a3-graph. I'd like to know are there some methods and ...

**1**

vote

**0**answers

90 views

### maximal sets of vertices that avoids a clique

I am looking for some known algorithm that finds, for a given graph, all the maximal sets of vertices that avoid a clique of some given size $k$. I'd prefer one written in MATLAB, but other languages ...

**4**

votes

**1**answer

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

**1**

vote

**2**answers

180 views

### Tight bound of Turan number for K_{1,t,t}

I'm looking for a tight bound for Turan number $ex_2(n,K_{1,t,t})$, where $K_{1,t,t}$ is the complete 3-partite graph with parts of size 1, t, and t.
The motivation is that we now $ex_2(n,K_{t,t})=O(...

**0**

votes

**1**answer

264 views

### Vertex cover of regular graph

(1.) How small can set $S$ of vertices in any regular undirected graph $G$ on $n$ vertices with degree $\Omega(n^\alpha)$ where $\alpha\in(0,1)$ can be such that every edge in the graph is incident on ...

**2**

votes

**1**answer

223 views

### Extremal combinatorics on bipartite graphs

One open question in extremal graph Theory is the so-called Zarankiewicz problem
(see for instance the wikipedia page), which ask for the maximum number of edges in a bipartite graph with a fixed ...

**6**

votes

**2**answers

302 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 of ...