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.
253 questions
10
votes
2
answers
452
views
Conjecture on minimum size of graph
Given a graph $G(V,E)$, let $\chi(G)$ be its chromatic number, and $\chi_1(G)$ its 1-improper chromatic number (meaning that each node can have at most 1 neighbor with the same color; or another way ...
- 23.7k
3
votes
1
answer
139
views
Turán density of an unbalanced complete $r$-partite $r$-graph
In a survey by Füredi and Simonovits called "The history of degenerate (bipartite) extremal graph problems," Theorem 10.5 states the following:
Let $\mathcal K = K^{(r)}(a_1, \dots, a_r)$ ...
- 783
4
votes
2
answers
2k
views
The number of monochromatic triangles
It is well known that the minimum number of monochromatic triangles in a red/blue coloring of the edges of the complete graph $K_n$ is given by Goodman's formula
$$M(n)=\binom n3-\left\lfloor\frac n2\...
- 7,013
4
votes
3
answers
432
views
How to show that random graphs cannot be embedded with short edges
For each (not necessarily planar) embedding of a graph in $\mathbb{R}^k$ one can calculate the ratio
$$\gamma = \frac{\textsf{mean Euclidean length of edges}}{\textsf{mean Euclidean distance between ...
4
votes
0
answers
251
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$ ...
- 5,409
0
votes
0
answers
70
views
(Weakly) connected sets with large (out-)boundary
Let $\Gamma=(V,E)$ be a connected undirected graph with n vertices such that every vertex has degree at least $4$. Now draw arrows on some of the edges, in such a way that the in-degree of every ...
- 20.2k
2
votes
1
answer
155
views
Combinatorial process on multisets of integers
Edit: I prefer to formulate first the problem as Fedor Petrov suggests in the comments:
We are given a multiset $F$, initially containing only the single integer $h$. Sequentially, at each time step, ...
- 1,677
2
votes
0
answers
108
views
What is the optimal upper bound of $|T_1|+|T_2|+|T_3|$ if $T_1, T_2, T_3$ are trees covering a planar graph
By a classical theorem of Nash-Williams, the edges of every connected $n$-vertex planar graph can be covered by three trees $T_1,T_2$ and $T_3$. Does anyone know of any results from an article or a ...
- 39
2
votes
0
answers
55
views
Expectation of Hadwiger number of a random graph
For any integer $n$, let ${\cal G}_n$ denote the set of simple, undirected graphs $G = (V, E)$ where $V = \{1,\ldots,n\}$. The Hadwiger number $\eta(G)$ of a finite graph $G$ is the maximum integer $m$...
- 48.9k
1
vote
0
answers
78
views
Expected value of the difference of the Hadwiger number and the chromatic number
If $G$ is a finite, simple, undirected graph, its Hadwiger number $\eta(G)$ is the maximum integer $n$ such that $K_n$ is a minor of $G$. Given any integer $k>0$ let $E_k$ be the expected value of ...
- 48.9k
6
votes
2
answers
426
views
Snake algorithm that minimizes straight lines
How can I find the non-self-intersecting loop that uses the least amount of straight lines (curves left/right as often as possible every turn) and still loops back on itself?
Here's an example we have ...
- 13.4k
17
votes
3
answers
464
views
Graph that minimizes the number of b/w colorings where white vertices have an odd number of black
motivated from a physical context, we are currently interested in the following graph coloring problem:
Given a connected graph $G_n$ with $n$ vertices, how many colorings exist such that all white ...
- 323
3
votes
1
answer
174
views
Minimum size of regular graph with no short cycles
For $d \geq 3$ (degree) and $r \geq 3$ (radius), say that a $d$-regular (finite, simple, non-oriented) graph $G$ is $r$-almost-tree if it contains no cycle of length $\leq 2 r$: in other words, we ...
- 12.7k
13
votes
2
answers
597
views
Graph in which no cycle has two crossing chords
Let $G$ be a graph which does not contain a simple cycle $v_1\ldots v_k$ and two "crossing" chords $v_iv_j$ and $v_pv_q$, $i<p<j<q$. An example of such graph is a triangulation of ...
- 1,319
1
vote
0
answers
123
views
Number of maximum matchings in bipartite graphs of positive surplus
Let $G$ be a simple bipartite graph with left part $L(G)$ and right part $R(G)$. For $S \subseteq L(G)$, denote $N(S)$ the set of neighbours of vertices of $S$. Define the surplus $s(G)$ as $\min_{S \...
- 5,590
2
votes
1
answer
114
views
Smallest size of graph covered by infinite tree
Let $T$ be the universal covering tree of some finite, connected, non-tree graph, and let $n_0(T)$ be the smallest positive integer such that there exists a graph $G$ (loops and multiple edges allowed)...
- 3,065
0
votes
1
answer
83
views
Making graphs isomorphic with edge additions/removals
Consider simple graphs on the same vertex set $[n]$. For two graphs $G, H$, let $d(G, H) = \min_{H' \sim H} |E(G) \triangle E(H')|$ — the smallest number of edge additions/removals needed to make $G$ ...
- 1,697
16
votes
1
answer
596
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 ...
- 37.7k
7
votes
0
answers
177
views
Szemerédi's regularity lemma for binary operations
Szemerédi's regularity lemma is an approximate structure theorem for
all large graphs (symmetric binary relations). There are versions for
multicolored graphs and directed graphs. Is there an ...
- 24.2k
10
votes
0
answers
176
views
Largest number of simple paths between two vertices
Let $G$ be a simple undirected graph, $f(v, u)$ be the number of simple paths between $u$ and $v$ in $G$, $f(G) = \max f(v, u)$ over all pairs of vertices $v, u \in G$.
A recent IOI problem utilized ...
- 5,590
4
votes
1
answer
230
views
Independence number of $C_4$-free graphs
It's well known that a $C_4$-free graph of order $n$ has average degree $O(\sqrt{n})$, and it follows that the independence number is $\Omega(\sqrt{n})$.
This bound cannot be improved over $\Theta(n^{\...
- 109k
3
votes
0
answers
93
views
Connected set of vertices having large boundary in a subset?
Let $\Gamma = (V,E)$ be a connected (undirected) graph where every vertex has degree $\geq 2$. Let $E'\supset E$ be a larger set of edges between elements of $V$ such that every vertex of $\Gamma'=(V,...
- 20.2k
2
votes
0
answers
99
views
Existence of a subcover with large boundary
Let $\mathscr{C}$ be a cover of $\mathbf{N}=\{1,2,\dotsc,N\}$ by finite subsets $S\in \mathscr{C}$ with $2\leq |S|\leq K$, where we write $|S|$ for the number of elements of $S$. Assume no element of $...
- 20.2k
3
votes
0
answers
70
views
Boundary differences in two graphs
Let $\Gamma, \Xi$ be two graphs with the same set of vertices $V$ with $n$ elements. Assume $\Gamma$ is connected. Write $\Gamma\cup \Xi$ (or $\Gamma\cap \Xi$) for the graph whose set of edges is the ...
- 20.2k
4
votes
0
answers
104
views
Maximal number of smallest circuits in a matroid
It is known (see here for example) that, in a simple graph of odd genus $g$ with $n$ vertices and $m$ edges, the number of cycles of lenght $g$ is at most $\frac{n(m-n+1)}{g}$.
Since this can be be ...
- 3,446
0
votes
1
answer
118
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 ...
- 767
0
votes
1
answer
66
views
Matching book thickness of the wheel graph $W_n$
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 ...
- 9,501
3
votes
0
answers
94
views
The pagenumber of subdivision of a complete graph
A book embedding of a graph $G$ consists of placing the vertices of $G$ on a spine and assigning edges of the graph to pages so that edges in the same page do not cross each other. The book thickness $...
- 4,713
0
votes
0
answers
102
views
4-cycles vs eigenvalue information on quasi-random graphs
My (philosophical) question arises from reading the wonderful paper of Chung-Graham-Wilson where the authors introduces the notion of quasi-random graphs.
The main purpose of the paper is to show ...
- 1,561
4
votes
0
answers
82
views
Expected number of bridges in a random subgraph
I am researching connectivity in random subgraphs and have come across the following problem.
A bridge between two vertices $a$ and $b$ of a graph $G$ is an edge $e$ such that removing $e$ from $G$ ...
- 175
8
votes
1
answer
392
views
Sum of degree differences for simple graphs
For a simple graph $G$ on $n$ vertices, let us define
$$\mathcal{I}_{n}(G)=\sum_{i,j=1}^{n}|\deg\ x_{i}-\deg\ x_{j}|^{3}.$$
I know that there are many different topological indices defined and ...
- 5,429
1
vote
1
answer
330
views
Density of bipartite $d$-degenerate graph
A graph $G$ is $d$-degenerate if every subgraph of $G$ contains a vertex of degree at most $d$. It is known that an $n$-vertex $d$-degenerate graph has at most $d(n-1)$ edges. However, if we are given ...
- 32.1k
1
vote
0
answers
53
views
At what aspect ratio does the Ruzsa-Szemeredi Theorem begin?
One of the many equivalent phrasings of the Ruzsa-Szemeredi theorem is as follows. Suppose one has a three-layered $n$-node graph $G = (V=L_1 \cup L_2 \cup L_3, E)$, and one can partition $E$ into ...
- 1,389
4
votes
2
answers
239
views
Population of P people, where each person knows K others, how many people mutually know each other
If you have a population of $P$ people, where each person knows $K$ others within the population (does not have to be mutual, i.e., if I know you, you don't necessarily know me), and $1<K<P$, ...
- 4,589
7
votes
1
answer
514
views
A proper definition of connectivity for hypergraphs
For usual graphs on $n$ vertices, a edge-minimal connected graph is nothing but a spanning tree of this graph. It is well-known that any spanning tree has $n-1$ edges.
I would like to know whether ...
- 48.9k
2
votes
1
answer
62
views
A simple equality for book embedding of two graphs
A book embedding of a graph $G$ consists of placing the vertices of $G$ on a spine and assigning edges of the graph to pages so that edges in the same page do not cross each other. The page number is ...
6
votes
2
answers
266
views
Lovasz local lemma for the edge model
In order to successfully apply the Lovasz local lemma, one needs the events to be relatively independent. This (sometimes) works well in the $G(n,p)$ model of random graphs, where the presence or ...
- 680
3
votes
1
answer
204
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 ...
- 253
2
votes
0
answers
137
views
How many edges can be in an unbalanced bipartite graph of girth $>6$?
Let $G = (V, E)$ be a bipartite graph with $n, m$ nodes in its bipartition and girth (shortest cycle length) $>6$.
There is a simple counting argument called the Moore Bounds that gives
$$|E| = O\...
- 1,389
4
votes
0
answers
145
views
Can the vertices of a planar graph of min degree 3 be covered with edges of average weight ( sum of degrees) at most 14?
Consider a planar graph where every vertex is incident to at least 3 edges, and assign to each edge a weight equal to the sum of the degrees of its endpoints.
If not, what is the smallest n so that ...
- 13.6k
4
votes
0
answers
116
views
Faithful Orthogonality Dimension of Kneser Graphs
Let us consider the complement of the Kneser graph with parameters $n$ and $n/4$. The vertex set of our graph $K$ is the set $\binom{[n]}{n/4}$ of $n/4$-subsets of $[n]$, and two vertices are joined ...
CommunityBot
- 1
3
votes
1
answer
305
views
Counting the forests obtainable by removing subtrees from binary trees
Let $B_h$ be the perfect binary tree having height $h$ (i.e. the binary tree with height $h$ in which all interior nodes have two children and all leaves have the same depth or same level).
For any ...
- 60.6k
2
votes
1
answer
164
views
Combinatorial optimization for a sequential random process on graphs
Let $G(V, E)$ be a simple graph with $|V|=n$, and let $h$ be an integer in $[n]$.
We repeat $h$-many times the following operation in a sequential fashion, where the graph may change at each round. ...
- 1,677
0
votes
0
answers
91
views
Properties of the collection of maximal independent sets of a graph
Let $G$ be a graph and define
$\mathscr{I}(G) = \{S \subset V(G)| S$ is a maximal indepedent set of $ G\}$
1. What is known about $\mathscr{I}(G)$?
What are some of the properties of $\mathscr{I}(G)...
- 1,034
3
votes
1
answer
121
views
The least number of edges to add to a tree that would force a certain number of edge-disjoint cycles
Let $c(n,k)$ be the least integer such that if $G$ is a simple graph on $n$ vertices with $n + c(n,k) - 1$ edges then $G$ has $k$ edge-disjoint cycles.
Clearly, $c(n, 1) = 1$ and it not very hard to ...
- 1,042
5
votes
1
answer
185
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 ...
- 96.4k
-1
votes
1
answer
94
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 ...
- 13.6k
9
votes
0
answers
156
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 ...
- 4,535
7
votes
1
answer
264
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 ...
- 4,535
7
votes
1
answer
410
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)...
- 4,535