Questions tagged [extremal-graph-theory]

The study of maximal or minimal graphs satisfying certain properties.

Filter by
Sorted by
Tagged with
0
votes
0answers
12 views

Different versions of Szemeredi's Regularity Lemma

I am having a hard time seeing how the statement of Szemeredi's Regularity Lemma used by Tao in this blogpost (Lemma 18) https://terrytao.wordpress.com/2010/11/27/nonstandard-analysis-as-a-completion-...
2
votes
0answers
41 views

Gallai partition

Gallai partition for edge coloring Reminder: If G is an edge-coloured complete graph on at least two vertices without a rainbow triangle, there is a nontrivial partition $P$ of $V(G)$ satisfying: (1) ...
0
votes
0answers
13 views

Applications of Hamiltonian Decompositions

A Hamiltonian decomposition of a given graph is a partition of the edges of the graph into Hamiltonian cycles. What are some applications of Hamiltonian decompositions? In what ways are they important ...
2
votes
1answer
38 views

How to understand if task on graph-theory has analytical solution?

Several Top Secret Objects are connected by an underground railway in such a way that each Object is directly connected to no more than k = 3 others, and from each Object you can get underground to ...
1
vote
1answer
37 views

Largest matrix satisfying a rank constraint

Consider a matrix with entries in $\{0,1\}$. The matrix is of dimension $R\times N$, where $R$ should be viewed as much larger than $N$. Each row of this matrix has exactly $N/2$ ones and the rest are ...
0
votes
0answers
20 views

How to find the optimal value of a function? Given a function and a closed area in parametric form. How can this exercise be solved?

Given the following function: $f(x,y) = x^3 - 3*x^2*y + 3*x*y^2 - y^3$ All the critical points on this curve are asked in the exercise. While calculating this with the code underneath. The Delta-test ...
0
votes
0answers
17 views

Understanding edge density bound in extremal graph theory

I am struggling to understand the following statement about extremal graphs: (edge) density is defined to be $\frac{e(G)}{n \choose 2}$, where e(G) is the number of edges in G, and n the number of ...
0
votes
1answer
51 views

Random Graph without K3,3 subgraph

Prove there is a constant $c > 0$ s.t. for every sufficiently large n, there exists a graph with n vertices and at least $cn^{3/2}$ edges, but no K3,3-subgraph. Hint: let p be a suitably chosen ...
1
vote
1answer
23 views

Maximum number of edges in a 'layered' graph

What is the maximum number of edges in an $n$-vertex, undirected simple graph whose vertex set has been split into $k$ consecutive layers (or subsets), such that the only edges in the graph go between ...
0
votes
0answers
52 views

ε-regular pair (A, B) includes $K_{3,3}$ subgraph

Let G consist of just a single ε-regular pair (A, B) of density d > 0, with |A| = |B| = l. Prove that for any d, we have that if ε is sufficiently small and ` is sufficiently large, then we can ...
0
votes
0answers
8 views

Proofing that $|EX(n,P_k)|$ = 1

Let $P_k$ be path at size k vertexes , and $EX(n,P_k)$ the group of all unqiue graphs that dosent contain $P_k$ as a sub graph and have maximum amount of edges possible. Need to proof that there is ...
2
votes
0answers
33 views

Upper bound on number of edges for graph with no C3 or C4

$G$ is a simple graph having $n$ vertices and $m$ edges. Show that if G has girth $\ge$ 5, then $$m \le \frac12 n \sqrt{n-1}$$. ***I am required to use a particular method: i.e. show first that $\...
1
vote
0answers
35 views

Max number of edges in a graph with n vertices without $P_3$

Find max number of edges in a graph with n vertices without a $P_3$ structure. *Note $P_3$ denotes the path with four vertices and three edges. I have two solutions: dividing n by 5 and forming a ...
0
votes
2answers
147 views

What is the maximum number of vertices of degree one that a binary tree with 10 vertices can have?

Full question as the title was a maximum of 150 characters. A binary tree is a connected graph with no cycles, where each vertex has a degree less than or equal to 3. What is the maximum number of ...
0
votes
1answer
43 views

Proving a result about a graph with $p$ connected components

I am trying to prove the following result: let $G=(V,A)$ be a graph with $p$ connected components. Prove that $$|V|-p\leq |A|\leq \binom{|V|-p+1}{2}$$ I have shown that if $G$ is a connected graph ...
0
votes
0answers
13 views

What is the order of the number of edges/vertices you need to remove from an H-minor free graph to make the graph planar?

What is the order of the number of edges/vertices you need to remove from an $H$-minor-free graph to make the graph planar (in terms of $H$)? If not all $H$ are known what $H$ are known? Similarly ...
0
votes
1answer
40 views

Upper-bound on number of connected components, given maximal degree

If an undirected graph $G = (V, E)$ has bounded degree $\deg(v) \leq d$ for each $v \in V$, how can we bound from above the number of connected components $C(G)$ of $G$? The following very rough proof ...
2
votes
0answers
53 views

Graphs with maximum and minimum Graph Energies

Given a graph $G$ with $n$ vertices, if its adjacency matrix $A$ has eigenvalues $\lambda_1 \geq \lambda_2 \geq . . . \geq \lambda_n$ then the energy is defined as: $$E(G) =\sum_{i=1}^{n} |\lambda_i|.$...
1
vote
1answer
65 views

Is the class of $k$-letter graphs finitely defined?

I am completely bamboozled by this problem, and although I believe the answer 'should' be yes, I cannot prove it for love nor money! I'll provide a couple of definitions for clarity's sake. A $k$-...
2
votes
0answers
30 views

Minimum Feedback Arc Set of Supergraph

Suppose we start from a directed graph $\mathcal{G}=(V,E)$, where $V$ is the set of vertices and $E\subset V \times V$ is the set of edges. Let $F \subset E$ be the solution to the minimum feedback ...
1
vote
1answer
46 views

Coloring an intersection graph of lines and a circle

Given a finite set of lines in the plane with no three meeting at a common point, and a circle that contain all intersection points of the lines in its interior, form a graph G whose vertices are the ...
1
vote
0answers
32 views

Maximal cliques bounding number of edges

I am struggling to solve the following problem. We have a simple (no loops or multiple edges) undirected graph with $n$ nodes. We are told that the graph does not contain any cliques with $m$ nodes ($...
1
vote
1answer
128 views

Upper bound on number of edges in graph with no clique of size k as subgraph

Let $G = (V, E)$ be an undirected graph such that $|V| = n$ and $G$ doesn't have a clique of size k as a subgraph. I need an upper bound on $|E|$. Any ideas? I'm hoping for $O(nk)$ but can't prove it. ...
0
votes
1answer
27 views

Directed graph, calculation of edges

I have a task "We have a graph G, which is directed and has 10 vertices. It has no parallel edges and has no loops. Also we know that G has 3 components and 5 strongly-connected components. What ...
2
votes
1answer
86 views

What is the maximum value of $|V|$

If $G=(V,E)$ is a connected graph with $|E|=17$ and $deg(v)>2$ for all vertices of graph $G$, what is the maximum value for $|V|=v$? $deg(v)\geq 3$ for all $v\in V$, $\sum_{v\in V} deg(v)=2|E|=2\...
1
vote
1answer
38 views

Let $(A,B)$ be a bipartition with $|A|=|B|=n$, show that if $\Delta(G)$ is at most $\epsilon^2n$ then the pair $(A,B)$ is $\epsilon$-regular

Suppose $G$ is a bipartite graph with bipartition $(A,B)$ with $|A|=|B|=n$, show that if the maximum degree of $G$ is at most $\epsilon^2n$ then the pair $(A,B)$ is $\epsilon$-regular. So here’s my ...
0
votes
0answers
68 views

prove that every graph on $n$ vertices, $n\geq 4$, with more than $2n^{3/2}$ edges has girth of at most 4

prove that every graph on $n$ vertices, $n\geq 4$, with more than $2n^{3/2}$ edges has girth of at most 4 Given the fact that every simple graph that satisfies $\sum_{v\in V} {{d(v)}\choose{2}} > (...
2
votes
1answer
83 views

Finding a 3-regular graph “with least no. of vertiecs” containing P6 as an induced-subgraph

Can you tell me a 3-regular graph with the least no of vertices, that contains P-6 as an induced subgraph? A 3-regular graph is one in which the degree of every vertex is 3. P-6 looks like: o--o--o--...
0
votes
0answers
33 views

Bipartite graph that does not contain a copy of Ks,r

Let 1 ≤ r ≤ s be constant integers. I need to show that any bipartite graph G = (V1, V2, E) with |V1| = n1 and |V2| = n2 (for n1 ≥ n2), that does not contain a copy of Ks,r as a subgraph, has |E| = O(...
0
votes
0answers
21 views

Certain Graph construction has no $K_4$ minor

I read that if one constructs a graph as follows: Start with $G_0=K_3$; Let $G_{k+1}$ be the graph formed by selecting two adjacent vertices $u, v$ , and adding a new vertex $w$ to $G_k$, and ...
0
votes
1answer
51 views

Smallest number of vertices in tree with specific degrees.

Find, with proof, the smallest number $r$ of vertices in a tree having two vertices of degree $3$, one vertex of degree $4$, and two vertices of degree $6$. Give an example of such a tree. Clearly, I ...
0
votes
1answer
42 views

smallest number of vertices of degree $1$ in tree with $3$ vertices of degree $4$ and $2$ of degree $5$

Find, with proof, the smallest number of vertices of degree $1$ in a tree with $3$ vertices of degree $4$ and $2$ of degree $5$. Provide an example of such a tree. I'm not sure how to find this. I ...
2
votes
1answer
23 views

Maximize number of edges in a directed graph with vertex degrees bounded by one

Given a finite simple directed graph $G = (V, A)$, I am looking for a subgraph $G' = (V', A')$ of $G$ such that, for each vertex $v'$ of $V'$, the in-degree and the out-degree of $v'$ are at most one, ...
0
votes
2answers
86 views

graph with $n$ vertices have having no subgraph isomorphic with $K_{2,t}$ can have at most $\frac{\sqrt{t-1}n^{3/2}+n}{2}$ edges

How would you prove that for each $t\geq 2$ any graph with $n$ vertices have having no subgraph isomorphic with $K_{2,t}$ can have at most $\frac{\sqrt{t-1}n^{3/2}+n}{2}$ edges? Wondering if proof via ...
0
votes
0answers
178 views

Graph with 45 vertices, what is the maximum number of edges in such graph?

I am a bit lost with this question. There is a graph with 45 vertices. If two vertices have the same degree, they are not connected by an edge. What is the maximal possible number of edges in such a ...
0
votes
1answer
77 views

Find the maximum number of 1s in matrix $A$ such that $A^2=0$ and elements of $A$ are either $0$ or $1$

Let $A$ be a square matrix(n by n) that consists of $1$s and $0$s. Find the maximum number of $1$s the matrix A can have if $A^2=0$. Attempt My only observation is that if $A_{ij}=1$, $j^{th}$ row and ...
2
votes
1answer
176 views

Lower and upper bound for the maximal number of edges of a graph

I am looking for a proof of the lower and upper bound for the maximal number of edges of a graph that does not contain the path $P_{r}$ with $1 \leq r < n$.
2
votes
1answer
72 views

Zarankiewicz problem maximum number of edges in a bipartite graph

I want to prove the lower and upper bound of the maximum number of edges in a bipartite graph that does not contain a $K_{s,t}$. I have found out that this is called the Zarankiewicz problem and but I ...
1
vote
1answer
67 views

Maximum Edges in a simple graph

A graph has 45 vertices. If two vertices are of the same degree, they are not connected by an edge. Find the maximal possible number of edges in such a graph. I have tried many different methods but ...
1
vote
2answers
69 views

Maximal possible edges in graph

A graph has 20 vertices. If two vertices are of same degree, they are not connected by an edge. Find the maximal possible number of edges in such a graph I tried constructing it through diagram but am ...
2
votes
0answers
38 views

How to characterize sail-free $3$-uniform hypergraph?

Please have a look at the problem below. Given a 3-uniform hypergraph $H=(V, E),$ the matching number $\nu(H)$ is the maximum number of pairwise-disjoint edges in $E(H) .$ The cover number $\tau(H)$ ...
5
votes
4answers
174 views

Smallest graph that is vertex-transitive but neither edge-transitive nor edge-flip-invariant?

Take any undirected graph $G$. We say that $G$ is vertex-transitive iff for every vertices $v,w$ there is an automorphism on $G$ that maps $v$ to $w$. We say that $G$ is edge-transitive iff for every ...
0
votes
0answers
22 views

Embedding lemma and Szemerédi regularity

Let $1>\delta>0$, $r$ a positive integer, $\epsilon_0=\frac{\delta^{r-1}}{r+1}$ and $m\in \mathbb{Z}$, such that $\epsilon_0m\geq 1$. If $0<\epsilon<\epsilon_0$ and $G\in \mathcal{G}(K_r,m,...
2
votes
1answer
63 views

Question about Turán's extremal theorem

I'm doing the exercise 5.10 at page 30 of Wilson's Introduction to Graph Theory. It says: Let $G$ be a simple graph on $2k$ vertices containing no triangles. Show, by induction on $k$, that $G$ has ...
9
votes
3answers
233 views

Let $A$ be a binary $n \times n$ matrix, such that $A^2=0$. What is the max num of $1$'s that $A$ could have?

I noticed: Fixing $A_{ij}=1$ would imply $i$-th column and $j$-th row are all $0$'s From there, I constructed a few matrices with small $n$ and hypothesized $f(n) = \lfloor{n/2}\rfloor \cdot \lceil{n/...
3
votes
1answer
81 views

What makes extremal problems in graph theory interesting?

I have recently started reading through lecture notes on graph theory, and it seems to me that after some introductory material the focus will often become extremal graph theory. Moreover, there are ...
4
votes
1answer
41 views

Does there exist any other graph class that has as many maximal cliques as Moon–Moser graphs?

According to wikipedia: The Turán graph $T(n,\lceil n/3\rceil )$ has $3^a2^b$ maximal cliques [...]. This is the largest number of maximal cliques possible among all n-vertex graphs regardless of the ...
0
votes
0answers
7 views

Why study inequalities between topological index of a graph?

I'am interested in the topological index of a graph. But l'am confused why we study inequalities between topological index ? For example , I have found many inequalities of the Harmonic index $H(G)=\...
2
votes
1answer
67 views

Prove that $R(Q_d) \leq 2^{3d}$, where $R(Q_d)$ is the Ramsey number of the $d$-dimensional hypercube $Q_d$.

I want to try a probabilistic proof for this problem. Please give some comments on this attempt at a proof. Let $G$ be our complete graph $K_{2^{3d}}$, with the edges colored red/blue randomly and ...
0
votes
0answers
49 views

Integer partition refinement, with minimal refinements

The setup I have two unordered partitions of N - example: 25 = 1 + 1 + 4 + 5 + 14 and 25 = 2 + 11 + 12. On each partitions I can only apply a refinement, which is to further partition one of its ...

1
2 3 4 5