Graphs with maximum size and lower bounded girth

Graphs with maximum size and lower bounded girth✩ E. Abajo, A. Diánez∗ Departamento de Matemática Aplicada I, Universidad de Sevilla, Sevilla, Spain a r t i c l e i n f o Article history: Received 18 November 2009 Received in revised form 28 June 2011 Accepted 27 September 2011 Keywords: Extremal function Extremal graphs Forbidden cycles Girth Cages abstract For integers n≥4 and ν≥n+1, let ex(ν; {C3, . . . , Cn})denote the maximum number of edges in a graph of order νand girth at least n+1. The {C3, . . . , Cn}-free graphs with order ν and size ex(ν; {C3, . . . , Cn})are called extremal graphs and denoted by EX(ν; {C3, . . . , Cn}). We prove that given an integer k≥0, for each n≥2 log2(k+2)there exist extremal graphs with νvertices, ν+kedges and minimum degree 1 or 2. Considering this idea we construct four infinite families of extremal graphs. We also see that minimal (r;g)-cages are the exclusive elements in EX(ν0(r,g); {C3, . . . , Cg−1}). 1. Introduction For undefined terminology and notation we refer the reader to [1]. Let V(G)and E(G)denote respectively the set of vertices and the set of edges of a graph G. The order of Gis denoted by ν=ν(G)and its size by e=e(G). The average degree of a graph is ¯ d=¯ d(G)=2e/n. The cycle of length n,n≥3, is denoted by Cn. Recall that the girth of a graph G,g=g(G), is the length of the shortest cycle in Gand if Gdoes not contain a cycle, we set g(G)= ∞. This work deals with ex(ν; {C3,...,Cn}), the maximum number of edges in a simple graph of order νand girth at least n+1. We refer to it as the extremal function. By EX(ν; {C3,C4,...,Cn})we denote the set of all simple graphs of order ν, girth at least n+1, and with ex(ν; {C3,C4,...,Cn})edges. Its elements are called extremal graphs. It is well known (see [2]) that ex(ν; {C3})= ⌊ν2/4⌋. Hence, we assume throughout this work that n≥4. The values of ex(ν; {C3,C4})for ν≤24 are given in [3], but proofs of some of them appear in [4]. The corresponding ones for 25 ≤ν≤30 are determined in [5]. For n∈ {5,6,7}lower bounds are provided in [6,7] and some exact values in [8]. More general results establish that ex(2n+2; {C3,...,Cn})=2n+4 for n≥12 (see [9]) and that ex(ν; {C3,...,Cn})=ν for n+1≤ν≤ ⌈3n−1 2⌉(see [10]). Due to the difficulty that is involved in the determination of the exact value of the extremal function, general characteristics of the extremal graphs are studied in the papers [10,11,3,9]. In this work we first determine general properties of the extremal graphs. In particular we prove in Theorem 2 that under certain conditions, the extremal graphs are quite similar to one another. That is, many of them are simply obtained by subdividing the edges of a certain simple graph or a multigraph until the forbidden cycles are avoided and the girth becomes as large as desired. Adopting this idea, we construct four infinite families of extremal graphs. To prove their extremality we make use of the next result obtained by Alon, et al. in [12]: ✩This research was supported by the Ministry of Education and Science, Spain, and the European Regional Development Fund (ERDF) under project MTM2008-06620-C03-02/MTM.; and under the Andalusian Government project P06-FQM-01649. ∗Corresponding author. E-mail addresses: [email protected] (E. Abajo), [email protected] (A. Diánez). 0893-9659/$ – 576 E. Abajo, A. Diánez / Applied Mathematics Letters 25 (2012) 575–579 Theorem A ([12]).For g ≥3and d >2, put ν0(d,g)=             1+d g−3 2 − i=0 (d−1)iif g is odd 2 g−2 2 − i=0 (d−1)iif g is even. A graph G with average degree ¯ d and girth g has at least ν0(¯ d,g)vertices. 2. Results Definition 1. Let k≥0 and n≥4 be integers. Let Gk(n)denote the set of all graphs Gsuch that e(G)−ν(G)=kand g(G) > n. To prove that this set is not empty it is enough to consider the graph formed by k+2 independent paths of length ⌊n/2⌋ + 1 with the same endvertices. It then makes sense to consider the minimum order of any graph in this set. Definition 2. Let k≥0 be an integer. For each n≥4 we define νk(n)=min{ν(G):G∈Gk(n)}. It is clear that ex(νk(n); {C3,...,Cn})≥νk(n)+kbut both the equality and the inequality are really possible. If k=n=4, it is known [3] that ex(9; {C3,C4})=12 and that ex(10; {C3,C4})=15. Therefore, ν4(4) > 9 and it is feasible to construct graphs in G4(4)with 10 vertices, for example, the graph obtained by removing an edge from the Petersen cage. This proves that ν4(4)=ν5(4)=10, and that no graph of G4(4)is extremal. Taking into account that the function ex(ν; {C3,...,Cn})increases strictly in ν, it is obvious that ex(ν; {C3,...,Cn})≥ ν+kfor every ν≥νk(n). Consequently the knowledge of the numbers νk(n)and νk+1(n)determines the set of orders ν such that the function ex(ν; {C3,C4,...,Cn})−νis a constant. Proposition 1. Let k ≥0and n ≥4be integers such that νk(n)<νk+1(n). Then, {ν:ex(ν; {C3,...,Cn})=ν+k}={ν:νk(n)≤ν < νk+1(n)}. The importance of the above defined numbers νk(n)is such that they allow one to change the difficult problem of the determination of the exact value of the extremal function ex(ν; {C3,...,Cn})to an easier one. In fact, the knowledge of two consecutive numbers νk(n), νk+1(n)provides general results on the function ex(ν; {C3,...,Cn}). The graphs of Gk(n)with minimum order νk(n)satisfy some particular properties. Proposition 2. Let k ≥0and n ≥4be integers. Every graph G in Gk(n)with order νk(n)has minimum degree δ(G)≥2and girth g(G)=n+1. Proof. Let Gbe a graph in the set Gk(n)with νk(n)vertices. The minimum degree of Gmust be at least 2, because otherwise there exists a vertex u∈V(G)with degree δ(u)=1 and the graph G′=G−ubelongs to Gk(n)and has number of vertices less than νk(n). Likewise, if g(G)=n+2, the graph G′obtained from Gby contracting one of its edges belongs to Gk(n)and satisfies ν(G′)=νk(n)−1.  This result implies that any graph in EX(νk(n); {C3,...,Cn})has exactly girth n+1, extending the ideas of the papers [10,11,3,9]. Returning on the values νk(n), we see next that they increase strictly in nbut not necessarily strictly in k. Moreover, as a consequence of Proposition 1 we can affirm that there are at most ⌊n/2⌋orders νsuch that ex(ν; {C3,...,Cn})−νremains constant. Lemma 1. For integers k ≥0and n ≥4the following hold: (i) νk(n)≤νk+1(n). (ii) νk+1(n)≤νk(n)+ ⌊n/2⌋. Proof. (i) By removing one edge from every graph in Gk+1(n)one obtains a graph in Gk(n)with the same order. This implies that νk(n)≤νk+1(n). (ii) Let G∈Gk(n)be a graph with order νk(n). Since g(G) > n, there exist u, v in Gsuch that dG(u, v) ≥ ⌈n/2⌉. The graph G′obtained from Gby adding a path of length ⌊n/2⌋ + 1 joining the vertices u, v belongs to Gk+1(n), and therefore, ν(G′)=νk(n)+ ⌊n/2⌋ ≥ νk+1(n). E. Abajo, A. Diánez / Applied Mathematics Letters 25 (2012) 575–579 577 Although we have mentioned that the set {ν:νk(n)≤ν < νk+1(n)}can be empty, this does not happen when n≥2 log2(k+2). Moreover, infinite extremal graphs Gsuch that e(G)−ν(G)=kcan be constructed by an adequate subdivision of edges until the forbidden cycles are avoided and the girth becomes as large as desired. Theorem 2. Let k ≥1be an integer. For all n ≥2 log2(k+2)there exists νsuch that: (i) ex(ν; {C3,...,Cn})=ν+k. (ii) Every graph of EX(ν; {C3,...,Cn})has minimum degree 1or 2. Proof. First we prove that the existence of a graph G∈Gk(n)such that δ(G)≥3 implies that n<2 log2(k+1). Let us assume that, for k≥1, there exists a graph Gin Gk(n)with δ(G)≥3 and maximum degree ∆(G)=∆. Let us denote by nithe number of vertices of degree iin G. Obviously, n3+n4+ · · · + n∆=ν(G)and 3n3+4n4+ · · · + ∆n∆= 2e(G)=2(ν(G)+k). We conclude that ν(G)=n3+n4+ · · · + n∆≤n3+2n4+ · · · + (∆−2)n∆=2k. On the other hand, since ¯ d(G)≥δ(G)≥3 and g(G)≥n+1, it follows from Theorem A that ν(G)≥3·2n/2−2 if nis even 2·(2(n+1)/2−1)if nis odd. Both inequalities concerning ν(G)imply that n<2 log2(k+1). (i) For given integers k≥0 and n≥2 log2(k+2), let G∈Gk+1(n)be any extremal graph with order νk+1(n). As we have just seen, and according to Proposition 2,Ghas a vertex xsuch that δ(x)=2. The graph G′=G−xbelongs to Gk(n)and therefore νk+1(n)−1=ν(G)≥νk(n). This inequality and Proposition 1 imply that at least for ν=νk(n)the equality ex(ν; {C3,...,Cn})=ν+kholds. (ii) Given k≥0 and n≥2 log2(k+2)the existence of an order νsuch that ex(ν; {C3,...,Cn})=ν+kis guaranteed from the previous remark. Then every graph G∈EX(ν; {C3,...,Cn})belongs to Gk(n)and its minimum degree δ(G)must be 1 or 2, because otherwise the assumption concerning nis contradicted as we have proved before.  In particular, by convenient subdivisions we present below four infinite families of extremal graphs. Theorem 3. For n ≥4and k ∈ {1,5,7,15}, we have ex(ak(n); {C3,...,Cn})=ak(n)+k, where the values of ak(n)are determined as follows: (i) if n ≥4,a1(n)= ⌈(3n+1)/2⌉; (ii) if n = 6,a5(n)=3n−2; (iii) if n = 6,7,8,9,10,12,16,18, a7(n)=⌊(7n−4)/2⌋if n ≡1,2,3(mod 6) (7n−2)/2if n ≡0,4(mod 6) (7n−7)/2if n ≡5(mod 6); (iv) a15(n)=⌊(45n−34)/8⌋if n ≥274 and n ≡0,1,2,4,6(mod 8) ⌊(45n−55)/8⌋if n ≥155 and n ≡3,5(mod 8) (45n−75)/8if n ≥7and n ≡7(mod 8). Proof. For given integers n≥4 and k∈ {1,5,7,15}, we consider the graph displayed in Fig. 1, taking into account that every edge is subdivided the indicated number of times according to its color. Since this graph belongs to the set Gk(n)and has order ak(n), it follows that ex(ak(n); {C3,...,Cn})≥ak(n)+k. The another inequality comes from the result in [12], since the assumption of the existence of graphs with girth at least n+1, order ak(n)and size strictly greater than ak(n)+kcontradicts Theorem A. If we extend the definition of ak(n)to being the order of the graphs in Fig. 1, then we can also affirm that ex(ak(n); {C3,...,Cn})≥ak(n)+kfor the excluded values of n. Notice that we have just constructed a family of extremal graphs by subdivisions of the multigraph formed by two vertices joined by three edges. In contrast, subdivisions of pseudographs can be avoided whenever the extremal graphs contain more than one cycle. Proposition 3. Let n ≥4and ν≥ ⌈(3n+1)/2⌉be integers. No graph in EX(ν; {C3,...,Cn})can be obtained by subdivisions of a pseudograph. 578 E. Abajo, A. Diánez / Applied Mathematics Letters 25 (2012) 575–579 Fig. 1. Four infinite families of extremal graphs. Proof. Assume that there exists an extremal {C3,...,Cn}-free graph G, with order ν(G)≥ ⌈(3n+1)/2⌉, which is a subdivision of a pseudograph. If we write k=e(G)−ν(G), from Theorem 3 it follows that k≥1. Clearly, Gcontains one cycle with m, (m≥n)consecutive vertices, x1,x2,...,xm, with degree 2. The graph G′=G−{x1,...,xm}belongs to Gk−1(n), and consequently, ν(G′)≥νk−1(n). From Proposition 1 it is known that νk+1(n) > ν(G)=ν(G′)+m≥ν(G′)+n≥νk−1(n)+n. This inequality contradicts Lemma 1(ii).  Theorem 2 and Proposition 3 let us conclude that some extremal graphs are not very different from each other, because many of them are simply obtained by subdividing the edges of a graph or multigraph until the forbidden cycles are avoided. Once the girth becomes as large as desired and the order νis such that νk(n) < ν < νk+1(n), the extremal graphs can also contain paths appended to some vertices of a cycle. It is known (see [3]) that the Petersen and the Hoffman–Singleton cages are the unique elements in EX(10; {C3,C4})and EX(50; {C3,C4})respectively. This result can be extended, and in fact minimal (r;g)-cages are the exclusive elements in EX(ν0(r,g); {C3,...,Cg−1}). To prove this, we take into consideration that the authors of [12] define Λ(G)=∏u∈V(G)(δ(u)− 1) δ(u) 2e(G)and affirm that any graph Gwith girth gverifies ν(G)≥ν0(Λ(G)+1,g)≥ν0(¯ d(G), g). (1) Taking into account that F(x)=xlog(x−1)is a convex function and consequently for any x0≥2 the inequality F(x)≥F(x0)+F′(x0)(x−x0)holds, it can be proved that Λ(G)+1=¯ d(G)if and only if Gis a regular graph. Theorem 4. Let r ≥3and g ≥5be given integers. If there exists a minimal (r;g)-cage with order ν0(r;g), then EX(ν0(r;g); {C3,...,Cg−1})= {minimal (r;g)-cages}. Proof. Let us assume that r≥3 and g≥5 are integers such that (r;g)-cages are minimal with order ν0(r;g). First, to prove that these graphs belong to the family EX(ν0(r;g); {C3,...,Cg−1}), it is enough to combine Theorem A and the strictly increasing function ν0(d,g). Second, any non-regular graph G∈EX(ν0(r;g); {C3,...,Cg−1})satisfies Λ(G)+1>¯ d(G)=rand contradicts inequality (1). References [1] G. Chartrand, L. Lesniak, Graphs and Digraphs, third ed., Chapman and Hall, London, UK, 1996. [2] P. Turán, On an extremal problem in graph theory, Math. Fiz. Lapok 48 (1941) 436–452. E. Abajo, A. Diánez / Applied Mathematics Letters 25 (2012) 575–579 579 [3] D.K. Garnick, Y.H.H. Kwong, F. Lazebnik, Extremal graphs without three-cycles or four-cycles, J. Graph Theory 17 (1993) 633–645. [4] D.K. Garnick, Y.H.H. Kwong, F. Lazebnik, Algorithmic search for extremal graphs of girth five, in: Y. Alavi, A. Schwenk (Eds.), Proceedings of the Seventh Quadrennial International Conference on the Theory and Applications of Graphs, WMU, (1992), Volume 2, John Wiley and Sons, New York, 1995, pp. 697–709. [5] D.K. Garnick, N.A. Nieuwejaar, Non-isomorphic extremal graphs without three-cycles or four-cycles, J. Combin. Math. Combin. Comput. 12 (1992) 33–56. [6] J. Tang, Y. Lin, C. Balbuena, M. Miller, Calculating the extremal number ex(ν; {C3,C4,...,Cn}), Discrete Appl. Math. 157 (2009) 2198–2206. [7] E. Abajo, C. Balbuena, A. Diánez, New families of graphs without short cycles and large size, Discrete Appl. Math. 158 (2010) 1127–1135. [8] E. Abajo, A. Diánez, Exact values of ex(ν; {C3,C4,...,Cn}), Discrete Appl. Math. 158 (2010) 1869–1878. [9] F. Lazebnik, P. Wang, On the structure of extremal graphs of high girth, J. Graph Theory 26 (1997) 147–153. [10] C. Balbuena, M. Cera, A. Diánez, P. García-Vázquez, On the girth of the extremal graphs without shortest cycles, Discrete Math. 308 (23) (2008) 5682–5690. [11] C. Balbuena, P. García-Vázquez, On the minimum order of extremal graphs to have a prescribed girth, SIAM J. Discrete Math. 21 (2007) 251–257. [12] N. Alon, S. Hoory, N. Linial, The Moore bound for irregular graphs, Graphs Combin. 18 (2002) 53–57.