Questions tagged [extremal-graph-theory]

The study of maximal or minimal graphs satisfying certain properties.

Filter by
Sorted by
Tagged with
2 votes
0 answers
93 views

Maximal vertices of a connected k-regular bipartite graph

Call a graph "$k$-special" if it is a connected $k$-regular bipartite graph such that if $AB$ and $AC$ are edges, then there exists exactly one other vertex $D$ such that $BD$ and $CD$ are ...
username's user avatar
0 votes
1 answer
113 views

A generalization of Turan's theorem

The Turan's theorem gives a tight upper bound of the number of edges in a $K_n$-free graph. I didn't manage to find some information about the generalization of this theorem when we're asked to ...
Bertrand Haskell's user avatar
4 votes
2 answers
135 views

Showing graphs with more than $\lfloor\frac{n^2}{4}\rfloor$ edges have a $3$-cycle.

From "A Brief Introduction to Spectral Graph Theory" Exercise 1.2 states A graph on $n$ vertices that contains no 3-cycles has at most $\lfloor \frac{n^2}{4}\rfloor$ edges. My thought ...
Dair's user avatar
  • 3,074
0 votes
1 answer
31 views

Size of a minimal vertex cover as an expression in terms of vertices and edges

I am currently working on the following problem: Let $\tau(G)$ be the minimum size of a vertex cover of a graph $G=(V,E)$. Show that for $|V|=n$, $|E|=m$, we have $$\tau(G)\leq\frac{2mn}{2m+n}$$ I am ...
Zerakiin's user avatar
3 votes
1 answer
50 views

Making a Star Graph Claw-Free: Edge Addition Count

Let $S_{n}$ be a star with $n$ vertices; see Star graph. $S_4$ is called a claw. A claw-free graph is a graph in which no induced subgraph is a claw. My question is: starting from a star graph $S_n$, ...
licheng's user avatar
  • 2,216
2 votes
1 answer
64 views

Proof that the maximum number of edges of a 1-planar graph is 4n - 8

The Wikipedia article about 1-planar graphs says that the maximum number of edges in such graphs is $4n - 8$ Every 1-planar graph with n vertices has at most 4n − 8 edges.[4] More strongly, each 1-...
Hadi El Yakhni's user avatar
1 vote
1 answer
75 views

Graphs of maximum diameter of prescribed degree sequence.

I have two questions, both inspired by this thread, where it is asked what the maximum diameter a graph on $2023$ vertices and minimum degree 42 is. The answer is 140, which is approximately $\frac{3n}...
Mathieu Rundström's user avatar
3 votes
1 answer
55 views

Determine all graphs that contain $P_4$ but not $P_5$.

Let $P_n$ be a path with $n$ vertices. My question is as the title says: Determine all graphs that contain $P_4$ but not $P_5$. The question is derived from the first exercise on page 115 of a book ...
licheng's user avatar
  • 2,216
2 votes
1 answer
65 views

Let $G$ be a 5-regular graph with $|V(G)| = 10$. Prove that $G$ has a perfect matching.

I’ve made several attempts at this but can’t quite get there. We can use the fact that $\nu ~(G) \leq \tau ~(G)$ to bound the matching number of $G$. $|E(G)| = 25$, so if $G$ is 5-regular we require a ...
mr. man's user avatar
  • 115
0 votes
1 answer
33 views

Find the maximum number of edges in a planar subgraph of G

Kuratowski's theorem states that a graph G is non-planar if and only if G has either $K_5$ or $K_{3,3}$ as a minor. Clearly this graph contains two $K_5$ minors, so our maximum non planar subgraph ...
mr. man's user avatar
  • 115
0 votes
0 answers
19 views

To explain the appearance of an imaginary unit in the algebraic form of a record

In my code, I am looking for an algebraic expression for the maximum point. There is an imaginary unit in it, although when substituting numerical variables, I see that the imaginary part is not there....
Vaisala's user avatar
  • 17
0 votes
0 answers
24 views

Bounds on chromatic number in terms of chromatic numbers of subgraphs.

Suppose we have a graph G of the form $G = G1 \cup G2$, and graphs G1 and G2 are defined by $V(G1) = V(G2)$. How can we describe the dynamics of the chromatic number of G in relation to the chromatic ...
mr. man's user avatar
  • 115
0 votes
1 answer
47 views

Using Euler formula to prove maximum number of lines in planar graph without triangles

Im trying to prove a planar graph without triangles with $ n \ge 3$ points has at most $2n-4$ edges. I want to solve this using the Euler formula, $n+f=m+2$. I've come to the conclusion that $f\le$ $m/...
Layla16's user avatar
  • 23
5 votes
1 answer
71 views

In a simple graph with $2m$ vertices and a unique perfect matching, prove that $|E(G)|$ is bounded by $m^2$.

I have been trying to solve this question, it was already asked but the response seems to have some issues. The accepted answer implies that if a graph has a cycle of length 4, this implies that it ...
mr. man's user avatar
  • 115
1 vote
0 answers
37 views

The edit distance from a large complete $p$-partite graph to the Turan graph

Let $K=K(V_1,V_2,\cdots,V_p)$ be a $p$-partite complete graph on $n$ vertices and $T_p(n)$ be the Turan graph. Show that: if $e(K)\geq e(T_r(n))-t$ then $$\sum_{k=1}^p\left(|V_k|-\frac{n}{p}\right)^2\...
Zeta's user avatar
  • 153
1 vote
0 answers
26 views

Is there a linear bound on the sum over branch vertices of minimum distances to leaves multiplied by outdegree?

Let's consider a directed rooted tree $T$ and define a function $f\colon V(T) \to \mathbb N$ equal for each vertex $v$ to the distance to the nearest leaf (in the subtree with root $v$). Formally $$f(...
Smylic's user avatar
  • 6,670
0 votes
0 answers
10 views

Could someone help me answer the following question using the Markov inequality and Chebyshev's inequality? I appreciate your assistance in advance.

"Denote by $C(G)$ the largest number of vertices in a component of a graph $G$. Show that if $p \ll 1/n$, then $C(G(n,p))\leq log⁡(n)$ with high probability. Demonstrate that for each $\...
Alicia Amorim's user avatar
1 vote
1 answer
103 views

Maximum independent set size

If I were to have a graph (without loops and parallel edges) having 10 vertices and 20 edges, what could be maximal possible size of an independent set? I've tried constructing a graph and checking ...
Jimmeh's user avatar
  • 89
2 votes
0 answers
36 views

The relationship between girth and size in graphs

I love the exercises 2.1.63 below (on page 78) in the West's textbook Introduction to Graph Theory. 2.1.63. Prove that every $n$-vertex graph with $n+1$ edges has girth at most $\lfloor(2 n+2) / 3\...
licheng's user avatar
  • 2,216
1 vote
1 answer
57 views

Maximum number of edges in a Line Graph L(G)

The line graph 𝐿(𝐺) of a simple graph 𝐺 is defined as follows: There is exactly one vertex 𝑣(𝑒) in 𝐿(𝐺) for each edge 𝑒 in 𝐺. That being said, how can I prove that the maximum number of edges ...
Felipe 杨睿's user avatar
0 votes
0 answers
58 views

Lower bound for couples of disjoint sets in some partitions of the power set

Now crossposted at Mathoverflow. Consider partitions $\mathcal{F}=\{\mathcal{A_1},\ldots,\mathcal{A_n} \}$ of the powerset without the empty set element $Q = \mathcal{P}([n]) \setminus \{\emptyset\}$. ...
Fabius Wiesner's user avatar
2 votes
1 answer
95 views

Minimum vertex number that admits linear $d$-regular $k$-uniform hypergraph

$\newcommand\LRU{\mathrm{LRU}}\newcommand\tA{\mathrm{A}}\newcommand\tB{\mathrm{B}}\newcommand\tC{\mathrm{C}}\newcommand\tD{\mathrm{D}}\newcommand\tE{\mathrm{E}}$ For given integers $d>0$, $k>1$ ...
Matija's user avatar
  • 3,251
2 votes
1 answer
111 views

Maximum number of vertices with degree three in maximal bipartite planar graphs

A bipartite graph $G$ is a graph where each cycle has an even length. If $G$ can be drawn on the plane without any crossings of edges, $G$ is called planar. $G$ is called maximal planar bipartite if ...
licheng's user avatar
  • 2,216
5 votes
1 answer
223 views

Why does a 3-regular planar graph of diameter 3 have at most 12 vertices?

Today, I saw an interesting exercise on page 224 of the West textbook "Introduction to Graph Theory". 6.1.15. Construct a 3-regular planar graph of diameter 3 with 12 vertices. (Comment: T. ...
licheng's user avatar
  • 2,216
0 votes
0 answers
17 views

Maximal planar graphs with minimum independent sets

The lower bound is known to follow immediately from the Four Color Theorem. Theorem 1. If $G$ is a planar graph with order $n$, then $\alpha(G) \geq \frac{n}{4}$. The lower bound in Theorem 1 is sharp....
licheng's user avatar
  • 2,216
0 votes
0 answers
7 views

What's the $p$-th power of a $k$-uniform tight cycle?

I understand that in a graph when there's a cycle, the $p$-th power of the cycle is when all vertices at a distance of at most $p$ from each other (on the base cycle) are joined with edges. A $k$-...
kleinbottle's user avatar
1 vote
1 answer
31 views

Edge colouring distinguishing by sums for a complete graph

Let $G=(V_G,E_G)$ will be a simple graph and $f:E\to\{1,...,k\}$ will be edge $k-$coloring. Denote $\sigma_f(x) = \sum_{xy\in E_G}f(xy)$ for $x \in V_G$ Consider a parameter $s(G) = \min\{k:\exists k-\...
MI00's user avatar
  • 187
2 votes
1 answer
87 views

Large chromatic number implies a clique (weakened Hadwiger's conjecture)

This is an exercise from chapter 7 of Diestel's 'Graph theory': Show that there exists a function $f$ such that each graph $G$ of chromatic number at least $f(r)$ contains a $K_r$ minor. My attempts ...
Isomorphism's user avatar
3 votes
2 answers
167 views

Maximum number of sizes of maximal cliques for a graph?

I was wondering what is the maximum possible number of distinct sizes of maximal cliques in a graph with fixed order $N$, and if anyone can share or point me to a proof or literature on this topic. To ...
graphic3's user avatar
0 votes
0 answers
23 views

Graphs with large diameters and small clique numbers

Are there any results on connected graphs with large diameters and small clique numbers? I am particularly interested interested in the maximum number of edges on graph with $n$ vertices, minimum ...
ethereal_sideman's user avatar
3 votes
2 answers
123 views

Minimum & maximum options for simple graph connected component

Let $G = \langle V, E \rangle$ be a simple graph with no simple circles. Suppose that $|E| = 11$ s.t for each $u \in V : deg(u) \in$ {$1, 2, 3$}. Moreover, there are exactly $10$ vertices with ...
X4J's user avatar
  • 1,015
0 votes
0 answers
67 views

A question on the proof of Erdős, Kleitman and Rothschild

I'am currently working my way through the proof of Erdős, Kleitman and Rothschild on the Asymptotic Enumeration of $K_n$-free Graphs (see https://users.renyi.hu/~p_erdos/1976-03.pdf). In particular I ...
Jonas's user avatar
  • 75
3 votes
1 answer
121 views

Construction of a graph $G$ with $\lvert V(G)\rvert = 13$ vertices and minimum degree of every vertex $\delta_0 = 3$ aiming to maximize its diameter

How would you construct a connected undirected graph $G$ to attain the longest diameter $d =\text{diam}(G)$ (i.e. the longest distance between any pairs of vertices in $G$) possible? Parameters $G$ ...
user avatar
3 votes
0 answers
98 views

An extremal problem concerning sizes and connectivity.

Inspired by this question, we can ask a more general question. Question 1. Let $G$ be a connected graph with $n$ vertices and $m$ edges. Let $C$ be a cycle of $G$ such that after deleting all edges ...
licheng's user avatar
  • 2,216
0 votes
0 answers
34 views

Name of a specific graph with fixed distance and degree

I was trying to come up with a graph that maximizes the number of nodes such that there exists a path between any two nodes that is length 2, and the degree of each node is 10. Then I tried to ...
meerkat mezmo's user avatar
0 votes
1 answer
63 views

Find such minimal $n$ that everybody from $100-n$ people have a friend in group of n people.

There's 100 people in the company. For every group with 10 members there's at least one triplet of pairwise friends (on the graph it would look like a triangle). Find such minimal $n$ that the ...
Nikita Artemenko's user avatar
2 votes
1 answer
361 views

Proof clarification: if $G$ is a simple graph with $2n$ vertices, $n^2$ edges and no triangles, then $G$ is the complete bipartite graph $K_{n, n}$

Let $G$ be a simple graph with $2n$ vertices and $n^2$ edges. If $G$ has no triangles, then $G$ is the complete bipartite graph $K_{n,n}$. I stumbled upon this proof for the result above, and I've ...
Nebzat's user avatar
  • 135
1 vote
0 answers
20 views

Show that there can be an exponential number of maximal cliques in a disk intersection graph

This is Exercise 14 of "Efficient graph representations" (Spinrad), Chapter 3: Show that there can be exponentially many maximal cliques in a disk intersection graph. The "canonical&...
pyridoxal_trigeminus's user avatar
0 votes
1 answer
74 views

minimum degree of 2-connected graph

If we have a 2-connected graph G, then can we say that δ(G) > k(G)? I need that in order to use Halin's theorem. Can we have then a more general relation between k-connected graphs and their ...
macmacmac's user avatar
3 votes
1 answer
190 views

What is the maximum number of distinct edges that can be contained in a cycle in a $k$-connected graph?

I know the theorem below. Theorem. (Dirac [1960]) If $G$ is a $k$-connected graph (with $k \geq 2$ ), and $S$ is a set of $k$ vertices in $G$, then $G$ has a cycle including $S$ in its vertex set. ...
licheng's user avatar
  • 2,216
1 vote
1 answer
90 views

Graph Optimization Problems

I'm having a bit of trouble finding any references in the literature about optimizing functions defined on the set of graphs, i.e. in particular where the number of vertices is not fixed. For example, ...
user81327's user avatar
  • 441
2 votes
1 answer
92 views

Smallest graph with automorphism group $PSL(2,7)$

What is the minimal number of vertices of a graph $\Gamma$ such that $\Gamma$ has automorphism group $PSL(2,7)$, the finite simple group of order $168$? Better yet, what is this graph? Basically I am ...
Eric Kubischta's user avatar
0 votes
0 answers
61 views

Lower bound for the maximal complete subgraphs with all edges of the same color, for a complete graph

Consider the complete graph on $n$ vertices, and all possible graphs that can be obtained from it by coloring its edges with exactly $n$ colors. Given one of these colored graphs, we can determine the ...
Fabius Wiesner's user avatar
0 votes
0 answers
40 views

Proving existence of $d$-regular subgraph

Show that for every $\epsilon > 0$, there exists a $\delta = \delta(\epsilon) \geq 0$ and $n_0 = n_0(\epsilon)$ such that every graph $G = (V,E)$ with $n > n_0$ vertices and at least $\epsilon n^...
Piglet's user avatar
  • 335
1 vote
0 answers
59 views

Triangle-free graphs on a set $V$ of $n$ labeled vertices

Prove that the number of triangle-free graphs on a set $V$ of $n$ labeled vertices is $2^{(\frac{1}{4} + o(1))n^2}$ where the $o(1)$ term tends to $0$ as $n \to \infty$. I have a few ideas, but not ...
Piglet's user avatar
  • 335
0 votes
0 answers
44 views

Find (with proof) the smallest 3-regular simple graph G with κ(G) = 1.

So, my approach involves taking a star graph of order 3, and then taking considering the vertex in the middle to be the cut-vertex. Consequently, I cultivate the graph with 2 components in mind, the ...
Joe Santino's user avatar
0 votes
0 answers
34 views

Question about "growing layers of a planar graphs"

Given a planar graph $G$ k nodes $S$ of $G$ construct "layers" $L_i$ for $i=0,1,...$ as follows $L_0=S$, having constructed layers $L_0,L_1,..,L_i$ layer $L_{i+1}$ consists of those nodes ...
Hao S's user avatar
  • 288
0 votes
1 answer
142 views

Seeking proof that the greedy algorithm is in fact the most optimal algorithm to construct graph with maximum variance in its degree distribution.

User inputs: number of nodes (n) and number of links (k). Objective: create an undirected (n,k) graph without multi-edges and without self loops that exhibits the maximum standard deviation in its ...
Aman Kabra's user avatar
0 votes
1 answer
250 views

Upper bound of graph diameter, using only degree of vertices

Let $G$ be a connected graph with $n$ vertices, and the degree of its vertices are $d_1,...,d_n$. I want to find an upper bound on the diameter of $G$, using only $n,d_1,...,d_n$. One result I know is ...
Rui Sun's user avatar
  • 117
2 votes
1 answer
49 views

Lower bound on Shannon capacity of a Cayley graph

I was reading up on the Shannon capacity of graphs and came across this article on the Shannon capacity of Cayley graphs. Though the article deals primarily with the linear Shannon capacity, defined ...
Piglet's user avatar
  • 335

1
2 3 4 5
7