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
4
votes
2answers
122 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\...
9
votes
1answer
306 views
+100

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 ...
0
votes
0answers
42 views

maximum radius for a $k$-set of vertices in a graph

this is a cross-post from mse here. Let $G$ be a connected graph and $S$ a subset of its vertices. Given a vertex $v$ of $G$ we define the $S$-eccentricity of $v$ as the largest distance between $v$ ...
4
votes
3answers
297 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 ...
0
votes
0answers
60 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 ...
2
votes
1answer
116 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, ...
2
votes
0answers
102 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 ...
2
votes
0answers
33 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$...
1
vote
0answers
63 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 ...
6
votes
2answers
320 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 ...
3
votes
1answer
73 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 ...
13
votes
2answers
494 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
vote
0answers
54 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 \...
17
votes
3answers
393 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 ...
2
votes
1answer
78 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)...
0
votes
1answer
73 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$ ...
14
votes
1answer
467 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 ...
7
votes
0answers
141 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 ...
9
votes
0answers
103 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 ...
3
votes
1answer
96 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^{\...
3
votes
0answers
68 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,...
3
votes
0answers
66 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 ...
2
votes
0answers
93 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 $...
2
votes
0answers
172 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 ...
4
votes
0answers
82 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 ...
0
votes
1answer
42 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 ...
2
votes
2answers
249 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$, ...
1
vote
0answers
47 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
326 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
61 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$ ...
8
votes
1answer
281 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
135 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
44 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
90 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
215 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
0answers
70 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 $...
2
votes
1answer
55 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
173 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
45 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
76 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
92 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
153 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
288 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
152 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
379 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
107 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
154 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
133 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
87 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 ...