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
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^{\...
- 9,501
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
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
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
2
votes
1
answer
300
views
Do sparse graphs contain a single regular pair?
An easy corollary of the Szemerédi Regularity Lemma is that dense graphs contain linear sized $\varepsilon$-regular bipartite subgraphs whose density is similar to that of the parent graph. As noted ...
- 805
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
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 ...
- 767
3
votes
2
answers
331
views
Existence of connected component with large boundary?
Question 1. Let $\Gamma=(V,E)$ be a connected
graph with $n$ vertices, all of degree $d\geq 4$. Assume every vertex has $d$ distinct neighbors. (We can think of $d$ as being much smaller than $n$, ...
- 20.2k
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
10
votes
2
answers
497
views
Graph metric approximating Euclidean metric
I've been reading Wolfram's recent articles about graph/mesh/grid structures as an analogy for physical space, and it seems to me that there will be a problem getting the notion of distance to work ...
- 119
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 ...
user153000
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 ...
- 1,190
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
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
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$, ...
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 $...
- 767
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 ...
- 767
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 ...
- 2,339
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 ...
- 111
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 ...
- 211
8
votes
2
answers
427
views
Chromatic number of $C_4$-free graphs
How large can the chromatic number of an $n$-vertex $C_4$-free graph be? If the maximum degree of the graph $G$ is $\Delta$, is there a bound of the form
$\chi(G) \leq O(\Delta/\log(\Delta))$ as in ...
- 428
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 ...
- 1,677
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
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 ...
- 121
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,034
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 ...
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 ...
-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 ...
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
368
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-degree ...
- 23.7k
1
vote
1
answer
137
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 ...
- 389
10
votes
1
answer
526
views
Maximum number of triangles no two of which have a common edge
For $n\in N_+$, define $f(n)$ to be the maximum number of triangles in a graph $G$ with $n$ vertices, taken over all $n$-vertex graphs having the property where no two triangles have a common edge.
Do ...
- 475
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$ ...
- 141
4
votes
0
answers
143
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 ...
- 13.2k
6
votes
0
answers
108
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 ...
- 42k
1
vote
2
answers
205
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 ...
- 1,389
6
votes
3
answers
4k
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 ...
- 389
3
votes
1
answer
766
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-...
- 9,114
4
votes
0
answers
125
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 ...
- 41
13
votes
0
answers
741
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 ...
- 29k
4
votes
0
answers
46
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 ...
- 736
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
3
votes
1
answer
179
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, ...
- 1,551
2
votes
0
answers
44
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\...
- 1,551
2
votes
1
answer
238
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 ...
- 393
4
votes
1
answer
183
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$, ...
- 968