On the Minimum Order of Extremal Graphs to have a Prescribed Girth

SIAM J. DISCRETE MATH.c 2007 Society for Industrial and Applied Mathematics Vol. 21, No. 1, pp. 251–257 ON THE MINIMUM ORDER OF EXTREMAL GRAPHS TO HAVE A PRESCRIBED GIRTH∗ C. BALBUENA†AND P. GARC´ IA–V´ AZQUEZ‡ Abstract. We show that any n-vertex extremal graph Gwithout cycles of length at most khas girth exactly k+1 if k≥6 and n>(2(k−2)k−2+k−5)/(k−3). This result provides an improvement of the asymptotical known result by Lazebnik and Wang [J. Graph Theory, 26 (1997), pp. 147–153] who proved thatthe girth is exactly k+1 if k≥12 and n≥2a2+a+1ka, where a=k−3−(k−2)/4. Moreover, we prove that the girth of Gis at most k+2ifn>(2(t−2)k−2+t−5)/(t−3), where t=(k+1)/2≥4. In general, for k≥5 we show that the girth of Gis at most 2k−4ifn≥2k−2. Key words. extremal graphs, girth, forbidden cycles, cages AMS subject classification. 05C35 DOI. 10.1137/060656747 1. Introduction. Throughout this paper, only undirected simple graphs without loops or multiple edges are considered. Unless otherwise stated, we follow [2] for terminology and definitions. Let V(G) and E(G) denote the set of vertices and the set of edges of a graph G, respectively. The order of Gis denoted by |V(G)|=nand the size by |E(G)|=e(G). The minimum length of a cycle contained in Gis the girth g(G)ofG. A cycle of minimum length is said to be a girdle and if Gdoes not contain a cycle, we set g(G)=∞.ByCrwe will denote a cycle of length r,r≥3. Let Fbe a family of graphs. The extremal number ex(n, F) is the maximum number of edges in a graph of order nthat does not contain any graph of Fas a subgraph. The graphs of order nand size ex(n, F) not containing any F∈Fas a subgraph are the extremal graphs and are denoted by EX(n, F). We refer to graphs from EX(n, F)asextremal F-free graphs of order n, or just extremal. By ex(n;{C3,C 4,...,C k}) we denote the maximum number of edges in a graph of order nand girth at least k+ 1, and by EX(n;{C3,C 4,...,C k}) we denote the set of all graphs of order n, girth at least k+ 1, and with ex(n;{C3,C 4,...,C k}) edges. Erd¨os and Sachs [3] showed that an r-regular graph of girth at least k+ 1 with the least possible number of vertices has girth equal to k+ 1. (A proof of this result can be found in Lov´asz [7, pp. 66, 384, 385, and the references therein].) These graphs are called (r;k+1)-cages. In this paper we consider a similar question asked by Garnick and Nieuwejaar in [5] on extremal graphs with a relatively large girth. Is there a constant csuch that for all k≥5 and all n≥ck, the girth of any extremal graph with girth ≥k+1isk+1? They give an affirmative answer for k= 4. Lazebnik and Wang [6] showed that the ∗Received by the editors April 7, 2006; accepted for publication (in revised form) October 11, 2006; published electronically April 6, 2007. This research was supported by the Ministry of Education and Science, Spain, and the European Regional Development Fund (ERDF) under project MTM200508990-C02-02. http://www.siam.org/journals/sidma/21-1/65674.html †Departament de Matem`atica Aplicada III, Universitat Polit`ecnica de Catalunya, Barcelona, Spain ([email protected]). ‡Departamento de Matem´atica Aplicada I, Universidad de Sevilla, Sevilla, Spain (pgvazquez@ us.es). 251 Downloaded 04/05/17 to 150.214.182.215. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php 252 C. BALBUENA AND P. GARC´ IA–V´ AZQUEZ answer is negative for c= 2 and affirmative if k= 5 or if nis large in comparison with k. More precisely they proved the following result. Theorem A. Let k≥12,a=k−3−(k−2)/4,n≥2a2+a+1ka, and G∈EX(n;{C3,C 4,...,C k}). Then the girth g(G)=k+1. In order to prove Theorem A, Lazebnik and Wang used the following result, which they also stated in [6]. Theorem B. Let k≥3,G∈EX(n;{C3,C 4,...,C k}), and the maximum degree be Δ(G)≥k. Then g(G)=k+1. Our main contribution to this problem is to provide an improvement of Theorem A. More precisely we prove that the girth of G∈EX(n;{C3,C 4,...,C k})isk+1 if either k= 3 and n≥5; or k= 4 and n≥9; or k= 5 and n≥8; or k= 6 and n≥171; or k≥7 and n≥2(k−2)k−2+k−5 k−3+1. This contribution contains the known results for k=3,4,5; see [4, 5, 6]. Furthermore, it gives an answer to the problem for k= 6 posed by Lazebnik and Wang [6], who asked to prove the girth of an extremal {C3,C 4,C 5,C 6}-free graph is 7. Moreover, we show that the girth of G∈EX(n;{C3,C 4,...,C k}) is at most 2k−4 provided that k≥5 and n≥2k−2. This clearly implies that for k= 6 the girth of an extremal graph is at most 8 for 10 ≤n≤170. Let t=(k+1)/2. We also prove that the girth of G∈EX(n;{C3,C 4,...,C k}) is at most k+2ifk≥7 and n≥2(t−2)k−2+t−5 t−3+1. From this result it follows for k= 7 that if n≥64, then g(G)≤9. 2. Main results. The set of neighbors of u∈V(G) is denoted by NG(u). The number of neighbors of uis the degree dG(u)ofuin G, or briefly d(u) when it is clear which graph is meant. The distance dG(x, y)inGof two vertices x,yis the length of a shortest x−ypath in G. The greatest distance between any two vertices in Gis the diameter D(G)ofG. Diameter and girth are related by g(G)≤2D(G)+1. Let e=xy be an edge of G. As usual we will denote by G/{e}=G/e the graph obtained from Gby contracting the edge einto a new vertex ve, which becomes adjacent to all the former neighbors of xand y. Taking into account that we dealt with simple graphs of girth at least 4 the resultant graph by any edge contraction remains simple. Throughout the paper k≥3 is an integer. We begin by proving a technical and useful lemma. Lemma 2.1. Let G∈EX (n;{C3,...,C k})have two distinct edges e1and e2 such that every cycle of Gcontaining both of them has a length of at least k+3. Then the girth is g(G)=k+1if the diameter is D(G/{e1,e 2})≥k−2. Proof. Let G∈EX (n;{C3,...,C k}) satisfy the hypothesis of the lemma and suppose that the girth is g(G)≥k+ 2. The graph G=G/{e1,e 2}has g(G)≥k+1 because by hypothesis any cycle passing through both edges e1and e2has a length of at least k+ 3. Let u,vbe two vertices of Gsuch that dG(u,v)=D(G); then by hypothesis dG(u,v)=D(G)≥k−2. Let us consider the graph G∗ obtained from Gby adding two new vertices x1,x 2and the three edges ux1,x 1x2, and x2v. We have g(G∗) = min{g(G),D(G)+3}≥k+1, |V(G∗)|=|V(G)| Downloaded 04/05/17 to 150.214.182.215. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php EXTREMAL GRAPHS WITH PRESCRIBED GIRTH 253 +2=n, and e(G∗)=e(G) + 1, which contradict the maximality of G. Therefore g(G)=k+1. As a first consequence of the above lemma, we obtain in the next theorem an upper bound for the girth of any extremal graph which contains the known result g=k+ 1 for k= 5; see [6]. Theorem 2.2. Let G∈EX (n;{C3,...,C k})be for k≥5and n≥2k−2. Then G has a girth of g(G)≤2k−4. Proof. Let G∈EX (n;{C3,...,C k}) satisfy the hypothesis of the theorem, and assume the girth of Gis g≥2k−2. Let C:u0u1···ug−1u0be a girdle in G, and notice that g≥k+ 3 because k≥5. The graph G=G/{u0u1,u 1u2}clearly has girth g(G)≥2k−4; hence the diameter is D(G)≥g(G)/2≥(2k−4)/2=k−2. By Lemma 2.1 we have g=g(G)=k+1, yielding 2k−2≤k+1, which is a contradiction because k≥5. Therefore the girth of Gis g≤2k−3. Assume the girth of Gis exactly g=2k−3. As n≥2k−2 the graph Gmust contain a vertex ynot belonging to C. Without loss of generality, suppose that u0yis an edge of G. Notice that uk−2and uk−1, both belonging to C, satisfy that dC(u0,u k−2)=dC(u0,u k−1)=k−2. Then both u0−uk−2and u0−uk−1paths contained in Cmust be the unique shortest u0−uk−2and u0−uk−1paths in G, because k−2=(g−1)/2. This implies that dG(y,uk−2)≥k−2 and dG(y,uk−1)≥k−2 so that every cycle, if any, containing both edges u0yand uk−2uk−1must have a length of at least g+1=2k−2, which is at least k+ 3 because k≥5. Now let G =G/{u0y,uk−2uk−1}. Clearly, D(G)≥ dG (u1,u k)=dG(u1,u k)=k−2. By Lemma 2.1 we obtain g(G)=g=k+ 1, i.e., 2k−3≤k+ 1, which is impossible for k≥5. Hence the girth of Gis at most 2k−4 and the theorem is valid. Next, we obtain the following result which is an improvement of Theorem A and also contains the known results for k=3,4,5; see [4, 5, 6]. Theorem 2.3. Let G∈EX (n;{C3,...,C k}). Then g(G)=k+1if either k=3 and n≥5;ork=4and n≥9;ork=5and n≥8;ork=6and n≥171;ork≥7 and n≥2(k−2)k−2+k−5 k−3+1. Proof. From Theorem 2.2 it follows that any graph G∈EX (n;{C3,C 4,C 5}) for n≥8 has girth of 6. Therefore we can assume k=3,4ork≥6. Let G∈ EX (n;{C3,...,C k}) and suppose that its girth is g(G)≥k+ 2. Then, by Theorem BwehaveΔ≤k−1, where Δ denotes the maximum degree of G. Let Dbe the diameter of Gand let us take two vertices x, y at distance dG(x, y)=D. Then D≤k−1 because otherwise by adding the edge xy to Gwe would obtain a graph G of order nhaving girth g(G)≥k+ 1 and more edges than G, which contradicts the maximality of G. Let us consider the two cases D=k−1 and D≤k−2 separately. Case 1. D=k−1. Define the set Nk−1 G(x)={y∈V(G):dG(x, y)=k−1}. Clearly, |Nk−1 G(x)|≥1, because y∈Nk−1 G(x). Let us see that |Nk−1 G(x)|=1. Let W={w∈V(G):dG(x, w)+dG(w,y)=k−1}and suppose that there exists a vertex u∈V(G)\W. Then dG(x, u)+dG(u, y)≥kor, in other words, all the possible paths passing through uthat connect xwith yhave a length of at least k. Take any vertex v∈NG(u) and consider the graph Gresulting by contracting the edge uv in G. The girth of this new graph is g(G)≥k+ 1 and the diameter D(G)=D=k−1. So let x,y∈V(G) be such that dG(x,y)=k−1, and denote by G∗the graph obtained from Gby adding a new vertex x∗and the edges Downloaded 04/05/17 to 150.214.182.215. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php 254 C. BALBUENA AND P. GARC´ IA–V´ AZQUEZ xx∗and x∗y. Clearly, |V(G∗)|=|V(G)|+1=n, and girth g(G∗)=k+ 1, but e(G∗)=e(G)+2 = e(G) + 1, which contradicts the maximality of G. Hence, V(G)=W, which readily implies that yis the only vertex at distance D=k−1 from xand the number of vertices at distance D−1=k−2 from xis at most Δ, since these vertices must be neighbors of y. Therefore, if k= 3, then n≤1+Δ+1≤1+k= 4, contradicting the hypothesis for this case. If k= 4, then n≤1+Δ+Δ+1≤2k= 8, contradicting again the hypothesis for this case. So assume that k≥6. As for 1 ≤i≤D−2=k−3, the maximum number of vertices at distance ifrom xis Δ(Δ −1)i−1, we obtain n≤1+Δ k−4  i=0 (Δ −1)i+Δ+1≤1+(k−1) k−4  i=0 (k−2)i+k =(k−1)(k−2)k−3−2 k−3+k <(k−1)(k−2)k−3−2 k−3+(k−2)k−3=2(k−2)k−2−2 k−3. This contradicts the hypothesis of the theorem, so g(G)=k+1 in the case D=k−1. Case 2. D≤k−2. Notice that k=3,4 are impossible for this case because D≥g/2≥(k+2)/2.Sowehavek≥6. Let x∗be a vertex of Gwith degree dG(x∗)=δ, where δis the minimum degree of G, and let us denote by (x∗) = max{dG(x∗,y):y∈V(G)}the eccentricity of x∗. As the diameter is the maximum of the eccentricities we have (x∗)≤D≤k−2. Suppose first that (x∗)≤k−3. As for 1 ≤i≤k−3, the maximum number of vertices at distance ifrom x∗is δ(Δ −1)i−1, it is immediate that n≤1+δ k−4  i=0 (Δ −1)i≤1+(k−1) k−4  i=0 (k−2)i≤(k−1)(k−2)k−3−2 k−3, which is a contradiction. Therefore (x∗)=k−2, which means D=k−2. Let us consider the set Nk−2 G(x∗)={y∈V(G):dG(x∗,y)=k−2}. Let us prove the following claim. Claim. Given any vertex y∈Nk−2 G(x∗), every neighbor of vertex yis at a distance of k−3 from x∗. Otherwise suppose that there exists a vertex y1∈Nk−2 G(x∗)∩NG(y). Let us denote by x∗=x0x1x2···xk−2=yany shortest x∗−ypath. Clearly, every cycle containing both edges x∗x1and yy1, if any, has a length of at least k+ 3 because k≥6. Then we consider the new graph Gobtained from Gby contracting the edges x∗x1and yy1. If the diameter of Gis D(G)=k−2, then by Lemma 2.1 we would have g(G)=k+ 1, which is a contradiction with our assumption g(G)≥k+2. Therefore D(G)=k−3, which implies that for all z∈N(x∗), dG(z,y)=k−3 for all y∈Nk−2 G(x∗). Consequently, the edge yy1and any vertex z∈NG(x∗) lies on a cycle in Gof length at most 2k−5, which is impossible for k= 6 because g≥k+2. Hence every neighbor of vertex yis at a distance of k−3 from x∗when k= 6 and the claim is true for this case. Furthermore, for k≥7wehavedG(vx∗x1,v yy1)=k−3, where vx∗x1and vyy1 denote the newly arising vertices by the contraction of the edges x∗x1and yy1. Besides, dG(vx∗x1)=dG(x∗)+dG(x1)−2≤δ+Δ−2≤2(Δ −1) and dG(vyy1)= Downloaded 04/05/17 to 150.214.182.215. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php EXTREMAL GRAPHS WITH PRESCRIBED GIRTH 255 dG(y)+dG(y1)≤2(Δ −1). Therefore, V(G)={vx∗x1}∪ k−3  i=1 Ni G(vx∗x1), where Ni G(vx∗x1) denotes the set of vertices of Gat a distance of ifrom vertex vx∗x1. Thus  Ni G(vx∗x1) ≤2(Δ −1)(Δ −1)i−1= 2(Δ −1)i, for i=1,...,k−3, and we get n=2+|V(G)|≤3+2 k−3  i=1 (Δ −1)i ≤3+2 k−3  i=1 (k−2)i =3+2(k−2)k−2−2(k−2) k−3=2(k−2)k−2+k−5 k−3, contradicting the hypothesis of the theorem. Thus, every vertex y∈Nk−2 G(x∗) has all its neighbors at distance k−3 from x∗and the claim holds. Hence, |Ni G(x∗)|≤δ(Δ−1)i−1, for i=1,...,k−3, and |Nk−2 G(x∗)|≤(Δ−1)k−3. Then, for k≥6wehave n≤1+δ k−4  i=0 (Δ −1)i+(Δ−1)k−3 ≤1+δ k−4  i=0 (k−2)i+(k−2)k−3 ≤(k−1)(k−2)k−3−2 k−3+(k−2)k−3=2(k−2)k−2−2 k−3. This contradicts the hypothesis of the theorem, so we conclude that g(G)= k+1. Next, the goal is to provide a lower bound on nin order to guarantee that the girth is at most k+2 for k≥7. To do that first we state that an extremal {C3,...,C k}-free graph with maximum degree Δ ≥(k+1)/2has necessarily a girth of at most k+2. Theorem 2.4. Let k≥7be an integer. Let Gbe a graph belonging to the family EX (n;{C3,...,C k})with a minimum degree of at least 2and maximum degree Δ. Then g(G)≤k+2if Δ≥(k+1)/2. Proof. Let G∈EX (n;{C3,...,C k}) satisfy the hypothesis of the theorem, and assume g(G)≥k+ 3. Let xbe a vertex of maximum degree Δ and let y1,y 2,...,y Δ be all the neighbors of x. Since dG(yi)≥2, for each i=1,...,Δ, there exists xi∈V(G)−xadjacent to yi. Notice also that xi=xjfor all i=j, since g(G)>4. Taking into account that g(G)≥k+ 3, we deduce that dG−x(xi,x j)≥g(G)−4≥ k−1, dG−x(yi,y j)≥g(G)−2≥k+ 1, and dG−x(xi,y j)≥g(G)−3≥kfor all i, j =1,...,Δ with i=j. Let G∗be the graph obtained from Gby first deleting the Δ−1 edges xy2,...,xy Δand second adding the new Δ edges y1x2,...,y Δ−1xΔ,y Δx1. Then G∗has order nand size e(G∗)=e(G) + 1. Since Gis extremal, G∗must contain a cycle of length at most k. Let us denote by C∗a shortest cycle in G∗(notice that Downloaded 04/05/17 to 150.214.182.215. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php 256 C. BALBUENA AND P. GARC´ IA–V´ AZQUEZ x∈ V(C∗), since xhas degree 1 in G∗). We denote by Cthe cycle x1y1x2y2···xΔyΔx1 which has length 2Δ ≥k+ 1. Observe that Cis an induced cycle of G∗, since xi is nonadjacent to yjin G, for any i=jand the only newly introduced edges are yixi+1 for i=1,...,Δ−1 and yΔx1. Moreover, C∗=C, since g(C)≥k+ 1 and g(C∗)≤k. So, we may express C∗=P1∪P2, where P1is the longest path whose edges belong to the set E(C∗)\E(C)⊆E(G−x), and P2is the rest of C∗. Notice that the endvertices of P1must belong to {x1,...,x Δ}∪{y1,...,y Δ}by the construction of P1. Observe also that P2contains at least one edge of E(C), because otherwise the cycle C∗would be contained in Gagainst the assumption g(G)≥k+ 3. If the endvertices of P1are xiand xjfor certain i, j ∈{1,2...,Δ}, then the edge yi−1xior xiyiand the edge yj−1xjor xjyjmust be contained in P2and then e(P2)≥2. This implies that |V(C∗)|=e(C∗)=e(P1)+e(P2)≥dG−x(xi,x j)+2≥k−1+2=k+1; a contradiction. If the endvertices of P1are xiand yi, for some i∈{1,...,Δ}, then e(P1)≥dG−x−{xiyi}(xi,y i)≥g(G)−1≥k+ 2 and hence |V(C∗)|=e(C∗)= e(P1)+e(P2)≥k+ 3, again a contradiction. Otherwise, e(P1)≥min{dG−x(yi,y j),d G−x(xi,y j):i, j =1,...,Δ and i=j}≥k, which implies |V(C∗)|=e(C∗)=e(P1)+e(P2)≥k+1>k, arriving at a contradiction. Hence, g(G)≤k+2. From Theorem 2.4 we derive the following sufficient condition in terms of the order for an extremal {C3,...,C k}-free graph to have girth at most k+2. Theorem 2.5. Let G∈EX (n;{C3,...,C k})be of a minimum degree of at least 2. Then the girth is g(G)≤k+2if k≥7and n≥2(t−2)k−2+t−5 t−3+1, where t=(k+1)/2. Proof.IfΔ≥(k+1)/2, then g(G)≤k+ 2 for k≥7 because of Theorem 2.4 and the theorem holds. Hence assume Δ ≤(k+1)/2−1 and g(G)≥k+ 3. Let t=(k+1)/2. As in the proof of Theorem 2.3 we consider two cases D=k−1 and D≤k−2 separately and repeat this proof but taking into account that now Δ≤t−1 instead of Δ ≤k−1. In this way we arrive at a contradiction, which implies g(G)≤k+ 2, and the theorem holds. As an immediate consequence of Theorems 2.3 and 2.5, the following information about the girth of any extremal {C3,...,C 7}-free graph is provided. Corollary 2.6. Let Gbe a graph belonging to the family EX (n;{C3,...,C 7}). Then the girth g(G)=8if n≥783, and the girth is g(G)≤9if n≥64. 3. Conclusions. Theorem 2.3 can be compared with Theorem A. Both results give a sufficient condition on the order of an extremal graph to contain a cycle of minimum length k+ 1. Recall that a=k−3−(k−2)/4; then for k≥12 we have 2a>(k−2)2. Hence 2a2+a+1 >2(k−2)2a+2 ≥2(k−2)(3k−6)/2, and thus n≥2a2+a+1ka>2(k−2)(3k−6)/2ka(which is much larger than the requirement obtained in Theorem 2.3), n>(2(k−2)k−2+k−5)/(k−3). Moreover, Theorems 2.2 and 2.3 provide information on the girth of any extremal {C3,C 4,C 5,C 6}-free graph G. The girth is g(G)=7ifn≥171, and the girth is g(G)≤8ifn≥10. It is known for r=3,4,5 that each (r; 8)-cage is the incidence graph of a projective geometry called generalized quadrangle; see the survey by Wong [8]. The order of each of these graphs is 30,80,170, respectively. As a referee suggests, Downloaded 04/05/17 to 150.214.182.215. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php EXTREMAL GRAPHS WITH PRESCRIBED GIRTH 257 it appears that a result of Alon, Hoory, and Linial [1] can be used to show these cages do belong to EX(n;{C3,C 4,C 5,C 6,C 7}). The question is if these cages are also {C3,C 4,C 5,C 6}-free extremal. We would like to suggest the following open problems. Problem 1. Prove or disprove that each (r;8)-cage for r=3,4,5is a graph belonging to EX (n;{C3,C 4,C 5,C 6}), for n=30,80,170. Problem 2. Is it possible to improve the lower bound on nin Theorem 2.3 for k≥7? Acknowledgments. We would like to express our thanks to the referees for their helpful comments and suggestions. REFERENCES [1] N. Alon, S. Hoory, and N. Linial,The Moore bound for irregular graphs, Graphs Combin., 18 (2002), pp. 53–57. [2] R. Diestel,Graph Theory, 3rd ed., Springer-Verlag, Berlin, 2005. [3] P. Erd¨ os and H. Sachs,Regul¨are Graphen gegebener Taillenweite mit minimaler Knotenzahl, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe, 12 (1963), pp. 251– 257. [4] D. K. Garnick, Y. H. H. Kwong, and F. Lazebnik,Extremal graphs without three-cycles or four-cycles, J. Graph Theory, 17 (1993), pp. 633–645. [5] D. K. Garnick and N. A. Nieuwejaar,Nonisomorphic extremal graphs without three-cycles or four-cycles, J. Combin. Math. Combin. Comput., 12 (1993), pp. 33–56. [6] F. Lazebnik and P. Wang,On the structure of extremal graphs of high girth, J. Graph Theory, 26 (1997), pp. 147–153. [7] L. Lov´ asz,Combinatorial Problems and Exercises, North–Holland, Amsterdam, 1979. [8] P. K. Wong,Cages—A survey, J. Graph Theory, 6 (1982), pp. 1–22. Downloaded 04/05/17 to 150.214.182.215. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php