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
1
vote
0answers
37 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 ...
8
votes
2answers
226 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 ...
4
votes
0answers
53 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$ ...
7
votes
1answer
260 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 ...
1
vote
1answer
93 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
vote
0answers
41 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 ...
0
votes
1answer
67 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 ...
4
votes
2answers
206 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$, ...
2
votes
1answer
53 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
2answers
164 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
votes
0answers
34 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\...
4
votes
0answers
66 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 ...
4
votes
0answers
90 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 ...
7
votes
1answer
125 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 ...
3
votes
1answer
267 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 ...
2
votes
1answer
146 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. ...
0
votes
0answers
83 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)...
7
votes
1answer
315 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 ...
3
votes
1answer
104 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 ...
3
votes
1answer
146 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
1answer
115 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
1answer
86 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
0answers
138 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 ...
7
votes
1answer
255 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
1answer
61 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
1answer
195 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
0answers
130 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
0answers
117 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
0answers
98 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
2answers
150 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
3answers
854 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
1answer
308 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
0answers
90 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 ...
11
votes
0answers
421 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
0answers
38 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
1answer
244 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
1answer
174 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
0answers
36 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
1answer
129 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 ...
3
votes
1answer
137 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
0answers
57 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
0answers
93 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
0answers
57 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
1answer
848 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
1answer
185 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
2answers
257 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
1answer
526 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
1answer
378 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
0answers
51 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
1answer
128 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 $...