Electronic Journal of Graph Theory and Applications 12 .
, 17Ae23 A refined TuraAn theorem Slobodan Filipovski Faculty of Mathematics.
Natural Sciences and Information Technologies University of Primorska.
GlagoljasUka 8 6000 Koper.
Slovenia filipovski@famnit.
Abstract Let G = (V.
E) be a finite undirected graph with vertex set V (G) of order |V (G)| = n and edge set E(G) of size |E(G)| = m.
Let OI = d1 Ou d2 Ou A A A Ou dn = be the degree sequence of the graph G.
A clique in a graph G is a complete subgraph of G.
The clique number of a graph G, denoted by O(G), is the order of a maximum clique of G.
In 1907 Mantel proved that a triangle2 free graph with n vertices can contain at most b n4 c edges.
In 1941 TuraAn generalized MantelAos result to graphs not containing cliques of size r by proving that graphs of order n that contain no induced Kr have at most .
Oe rOe1 ) n2 edges.
In this paper, we give new bounds for the maximum number of edges in a Kr -free graph G of order n, minimum degree , and maximum degree OI.
We show that, for the families of graphs having the above properties, our bounds are slightly better than the more general bounds of TuraAn.
Keywords: clique, extremal graphs.
TuraAn theorem, inequality Mathematics Subject Classification : 05C35 DOI: 10.
5614/ejgta.
Introduction Let G = (V.
E) be a finite undirected graph with vertex set V (G) of order |V (G)| = n and edge set E(G) of size |E(G)| = m.
Let OI = d1 Ou d2 Ou A A A Ou dn = be the degree sequence of the graph G.
A clique in a graph G is a complete subgraph of G.
The clique number of a graph G, denoted by O(G), is the order of a maximum clique of G.
Received: 21 February 2023.
Revised: 24 October 2023.
Accepted: 26 November 2023.
A refined TuraAn theorem Slobodan Filipovski In extremal graph theory one seeks extremal values of graph parameters for graphs belonging to families with prescribed properties.
One of the classical problems of extremal graph theory involves showing that a graph with sufficiently many edges must contain a specific substructure.
In this sense, an extremal graph with respect to a family of graphs {Hi }iOOI is a graph G of order n and maximum size m among all graphs of order n that do not contain any of the graphs {Hi }iOOI as induced subgraphs.
The well-known TuraAn graphs T .
, .
constitute examples of just this type of extremal graphs.
Namely, the TuraAn graph T .
, .
has the maximum possible number of edges among all graphs on n vertices which do not contain an induced .
-clique.
If r = 2, the TuraAn graph T .
, .
is an undirected graph in which no three vertices form a triangle of edges.
a triangle-free graph.
One of the first results concerning extremal triangle-free graphs is due to Mantel:
Theorem 1.
1 (.
If G is a triangle-free graph, then m O b n4 c.
Furthermore, the only triangle2 free graph with b n4 c edges is the complete bipartite graph Kb n2 c,d n2 e .
TuraAnAos generalization of MantelAos result to cliques of size r is perhaps the best known theorem of extremal graph theory:
Theorem 1.
2 (.
If a graph G on n vertices contains no copy of Kr , then it contains at most 1 Oe rOe1 In this paper we consider the size of the Kr -free graphs G.
Since O(G) O r Oe 1, we focus on the lower bounds of the clique number of the graph.
Myers and Liu in .
proved that for a graph G with n vertices and m edges it holds O(G) Ou n2 Oe 2m Edwards and Elphick in .
have improved this bound by proving that for a graph G with n vertices and degree sequence d1 Ou d2 Ou A A A Ou dn we have O(G) Ou q Pn i=1 di .
Independently.
Caro .
and Wei .
showed that O(G) Ou a n Oe d1 n Oe d2 n Oe dn Based on the above lower bounds of the clique number, we derive new bounds on the maximum number of edges in Kr -free graphs in terms of the order n and maximum and minimum degrees.
We show that the upper bounds on the maximum sizes of Kr -free graphs of specified maximum or minimum degrees given by our theorems are smaller than or equal to the upper bounds on the maximum sizes among all Kr -free graphs .
ot restricted to specific minimum and maximum degree.
derived by TuraAn.
A refined TuraAn theorem Slobodan Filipovski New upper bounds for the size of Kr -free graphs Let G be a Kr -free graph.
Between the clique number of G and r there exist a natural relation, that is, r Oe 1 Ou O(G).
Combining this inequality with the well-known bound O(G) Ou n2 nOe2m we easily prove the TuraAn theorem.
We notice that an improvement of the lower bounds of the clique number could improve the TuraAn theorem.
We start with an improvement of the inequality between the arithmetic and the geometric mean, published in .
Lemma 2.
If x and y are strictly positive real numbers, then .
Oe .
2 Ou2 2.
2 y 2 ) Proposition 2.
Let G be a graph with n vertices and m edges.
If OI is the maximum degree, is the minimum degree of G and O(G) is the clique number of the graph G, then O(G) Ou (OIO.
2 n 2(.
OeOI) 2 .
2 ) n2 Oe 2m Proof.
Let OI = d1 Ou d2 Ou A A A Ou dn = be the vertex-degree sequence of G.
From the CauchySchwarz inequality we have O(G).
Oe 2.
Ou a .
2 Oe 2.
= n Oe d1 n Oe d2 n Oe dn a (.
Oe dn ) .
Oe d2 ) A A A .
Oe d1 )) Ou n Oe d1 n Oe d2 n Oe dn n Oe dn n Oe d1 n Oe dn n Oe d1 Ou 1 a 1 = nOe2 n Oe d1 n Oe dn n Oe d1 n Oe dn The inequality in .
follows from Lemma 2.
1, setting x = n Oe OI and y = n Oe .
(OIO.
Remark 2.
Since 2(.
OeOI) 2 .
2 ) > 0 we get that the bound in .
is better than the existing bound given by Myers and Liu .
Theorem 2.
If G is a graph of order n, with maximum degree OI, minimum degree and if G contains no copy of Kr , then the size m of G is at most 2 (OIO.
2 1 2n(.
OeOI)2 .
2 ) n2 mO Oe Oe .
Proof.
The proof follows directly from r Oe 1 Ou O(G) and the inequality in .
A refined TuraAn theorem Slobodan Filipovski Remark 2.
It is clear that the bound in the above theorem is slightly better than the bound stated in the TuraAn theorem.
Let us observe that, if the gap between OI and is bigger, then the difference between ourand the exiting bound is more significant.
For example, if OI = n Oe 1 and = 1 we 2n3 Oe3n2 4 get m O 2 1 Oe rOe1 , where C = 2n 3 Oe4n2 4n > 1.
Next, we use the lower bound for the clique number given by Edwards and Elphick, .
, and the following refinement of the inequality between quadratic and arithmetic means published in .
Proposition 2.
If a1 , .
, an are n positive real numbers such that a21 A A A a2n 6= 0, then a1 A A A an 1 X .
a2i Oe .
21 A A A a2n ))2 a21 A A A a2n Ou 4n i=1 n2 a4i .
21 A A A a2n )2 Let E 2 be the variance of the numbers d21 , d22 , .
, d2n .
From the above inequality we obtain the following result.
Theorem 2.
Let G be a connected graph on n vertices, with maximum degree OI, minimum degree and let G contain no copy of Kr .
If E 2 is the variance of the squares of the degrees of G, n A E2.
mO 1Oe rOe1 Proof.
Setting ai = di in Proposition 2.
2 we get X .
2i Oe Mn1 )2 d21 A A A d2n Ou .
4n i=1 a4i M1 2 From d4i Mn1 O 2OI for each i = 1, 2, .
, n and from E = .
2i Oe Mn1 ) Ou n 8OI4 E .
Now, the desired inequality follows directly from .
we get the Remark 2.
From the bound in .
we can notice that among all graphs on a fixed number of vertices, fixed r, with fixed maximum and minimum degree, the graphs whose degrees are spread further away from the mean, have larger variance E 2 , thus have smaller size m.
In other words.
Kr -free graphs with larger irregularity have smaller size.
Li et al.
, .
introduced the generalized version of the first Zagreb index, defined as Zp (G) = M1p (G) = dp1 dp2 A A A dpn where p is a real number.
This graph invariant is nowadays known under the name general first Zagreb index, and has also been much investigated.
The lower bound for the clique number of G could be expressed in terms of the general first Zagreb indices.
A refined TuraAn theorem Slobodan Filipovski Proposition 2.
Let G be a graph on n vertices and let Zi be the general first Zagreb index.
Then O(G) Ou 1 Proof.
We have O(G) Ou a a n Oe d1 n Oe dn Oe dnn ) n.
Oe n ) O dk a dk Ou d1 a d = 2m , that is.
Remark 2.
From the power mean inequality we obtain PO 2m i .
i Zi Ou niOe1 .
Therefore O(G) Ou 1 i=1 n2 = n2 Oe2m , which is a well-known lower bound for O(G).
Theorem 2.
If G is a graph of order n and maximum degree OI, and G contains no copy of Kr , the size m of G is at most 2 Oe .
Oe OI) n Oen OI Oe .
Oe OI) Oe .
Proof.
Since G does not contain a copy of Kr , then O(G) O r Oe 1.
Thus, applying .
and the inequality between arithmetic and harmonic means, we get rOe1Ou .
Oe .
2 2 n Oe OI n Oe n Oe 2m OI which is equivalent to n2 Oe n Oe 2m OI Ou .
Oe .
Oe OI) .
Oe .
Oe OI) Oe 1 This last inequality implies the desired bound .
We prove next that the bound .
from Theorem 2.
3 applied to a graph with a specific OI is better than the more general bound of TuraAn, that is, we show that n2 Oe n OI Oe .
Oe OI) 1Oe rOe1 2(.
Oe .
Oe OI) Oe .
) A refined TuraAn theorem Slobodan Filipovski for all 1 O OI O n Oe 1.
The inequality .
is equivalent to the inequality .
Oe OI)(.
Oe .
Oe .
Oe OI) Oe .
Oe .
Oe OI) Oe 1
rOe1
S 1
, the inequality .
becomes Taking S = .
Oe .
Oe OI) Oe 1 and r Oe 1 = nOeOI Oe .
2 S Ou
S 1
The last inequality is equivalent to .
Oe .
2 Oe 2S.
Oe .
S 2 Ou 0, that is, .
Oe 1 Oe S)2 Ou 0, which is true.
Note that our bound matches TuraAnAos bound if n Oe 1 = S, that is, if r Oe 1 = nOeOI The proof of our next theorem is analogous to the proof of Theorem 2.
Theorem 2.
If G is a graph of order n and minimum degree , and G contains no copy of Kr , the size m of G is at most 2 Oe .
Oe ) n Oen Oe .
Oe ) Oe .
Theorems 2.
3 and 2.
4 yield the following obvious corollary.
Corollary 2.
The maximum number of edges in a graph G that contains no copy of Kr , having n vertices, maximum degree OI, and minimum degree , is bounded from above by 2 .
Oe .
Oe OI) n Oen OI Oe 2(.
Oe .
Oe OI) Oe .
2 n Oen .
Oe .
Oe ) Oe 2(.
Oe .
Oe ) Oe .
Acknowledgement This work is supported in part by the Slovenian Research Agency .
esearch program P1-0285 and research projects N1-0210.
J1-3001.
J1-3003.
J1-4414 and BI-VB/23-25-.
References