On the lambda '-optimality in graphs with odd girth g and even girth h

On the λ′-optimality in graphs with odd girth gand even girth h C. Balbuenaa,∗, P. García-Vázquezb, L.P. Montejanoa, J. Salasa aDepartament de Matemàtica Aplicada III, Universitat Politècnica de Catalunya, Campus Nord, Edifici C2, C/ Jordi Girona, 1-3, 08034 Barcelona, Spain bDepartamento de Matemática Aplicada I, Universidad de Sevilla, Avda. Reina Mercedes, 2, 41012 Sevilla, Spain a r t i c l e i n f o Article history: Received 16 June 2009 Received in revised form 10 January 2011 Accepted 14 January 2011 Keywords: Connectivity Restricted connectivity Girth pair Polarity graphs abstract For a connected graph G, the restricted edge-connectivity λ′(G)is defined as the minimum cardinality of an edge-cut over all edge-cuts Ssuch that there are no isolated vertices in G−S. A graph Gis said to be λ′-optimal if λ′(G)=ξ(G), where ξ(G)is the minimum edgedegree in Gdefined as ξ(G)=min{d(u)+d(v) −2:uv∈E(G)},d(u)denoting the degree of a vertex u. The main result of this paper is that graphs with odd girth gand finite even girth h≥g+3 of diameter at most h−4 are λ′-optimal. As a consequence polarity graphs are shown to be λ′-optimal. 1. Introduction Throughout this paper, only undirected simple graphs without loops or multiple edges are considered. Unless otherwise stated, we follow the book by Chartrand and Lesniak [1] for terminology and definitions. The diameter of G, denoted by diam(G), is the maximum distance over all pair of vertices. The degree of a vertex vis d(v) = |N(v)|, whereas δ=δ(G)is the minimum degree of G. The edge-connectivity λof a graph Gis defined as the minimum number of edges whose removal from Gproduces a disconnected graph. This parameter λgives the minimum cost to disrupt a network, but it does not take into account what remains after deletion. As a more refined index than edge-connectivity, restricted edge-connectivity λ′=λ′(G)was introduced by Esfahanian and Hakimi [2] as the minimum cardinality over all restricted edge-cuts S, such that there are no isolated vertices in G−S. A restricted edge-cut Sis called aλ′-cut if |S| = λ′. Obviously for any λ′-cut S, the graph G−Sconsists of exactly two components. A connected graph Gis called λ′-connected if λ′exists. Esfahanian and Hakimi [2] showed that each connected graph Gof order n(G)≥4 except a star, is λ′-connected and satisfies λ′≤ξ, where ξ=ξ(G)denotes the minimum edge-degree of Gdefined as ξ(G)=min{d(u)+d(v) −2:uv∈E(G)}. Furthermore, a λ′-connected graph is said to be λ′-optimal if λ′=ξ. Recent results on this property are obtained in [3–7]. The odd girth (even girth) of Gis the length of a shortest odd (even) cycle in G. In this work we are interested in studying graphs with girth pair (g,h), that is, with odd girth gand even girth h. If there is no odd (even) cycle in G, then the odd (even) girth of Gis taken as ∞. Let g=g(G)denote the smaller of the odd and even girths of a graph Gcontaining cycles, and let h=h(G)denote the larger. Then gis called the girth of G, and (g,h)is called the girth pair of G. Girth pairs were introduced by Harary and Kovács [8]. A lower bound on the order of a regular graph with girth pair (g,h), for odd gand even h≥g+3 was found in [9]. Sufficient conditions for a graph to have high connectivity in terms of the girth pair (g,h)have been given in [10–13]. The main result of this paper is the following theorem. ∗ Corresponding author. Tel.: +34 93 401 69 17; fax: +34 93 401 18 25. E-mail addresses: [email protected] (C. Balbuena), [email protected] (P. García-Vázquez), [email protected] (L.P. Montejano), [email protected] (J. Salas). 0893-9659/ doi:10.1016/j.aml.2011.01.015 1042 C. Balbuena et al. / Applied Mathematics Letters 24 (2011) 1041–1045 Theorem 1.1. Let G be a λ′-connected graph of minimum degree δand girth pair (g,h), odd g and even h with g +3≤h<∞. Then G is λ′-optimal if (i) diam(G)≤2if either g ≥5or g =3, δ ≥3and G has no triangle with all its vertices of degree 3; (ii) diam(G)≤h−4if either g ≥5and δ≥4or g =3and δ≥5. 2. Results on graphs with a given girth pair Let Gbe a graph with vertex set V=V(G)and edge set E=E(G). For u, v ∈V,d(u, v) =dG(u, v) denotes the distance between uand v. For S,F⊂V,d(S,F)=dG(S,F)=min{d(s,f):s∈S,f∈F}denotes the distance between Sand F. For every S⊂V, and every nonnegative integer r≥0,Nr(S)= {w∈V:d(w, S)=r}denotes the neighborhood of S at distance r. Observe that N0(S)=S. When r=1 we put simply N(S)instead of N1(S). We also use the following notation introduced in [4]. Let U,F⊂V. Then, [U,F]stands for the set of edges {uf ∈E:u∈ U,f∈F}. If U= {u}, then we write simply [u,F]instead of [{u},F]. Let Gbe λ′-connected. An arbitrary λ′-cut Swill be denoted by [V(C), V(C)], where Cand Care the two components of G−S. As there exist X⊂V(C)and X⊂V(C)such that both Xand Xare the endvertices of the edges of [V(C), V(C)], we can write [V(C), V(C)]=[X,X]. To prove Theorem 1.1, we need the following proposition, which shows that the even girth his a suitable index in order to study how far away a vertex of a non-λ′-optimal graph Gcan be from a set of vertices. Proposition 2.1. Let G be a λ′-connected graph of minimum degree δand girth pair (g,h), odd g and even h with g+3≤h<∞. Let [V(C), V(C)]=[X,X] ⊂ E be a λ′-cut, X ⊂V(C), X⊂V(C). If G is non-λ′-optimal, then there exists a vertex u ∈V(C) such that (i) d(u,X)≥1if either g ≥5or g =3, δ ≥3and G has no triangle with all its vertices of degree 3; (ii) d(u,X)≥(h−4)/2if either g ≥5and δ≥4or g =3and δ≥5. Proof. Let Gbe a λ′-connected graph, and let S= [X,X]be a λ′-cut, X⊂V(C)and X⊂V(C)being the sets of endvertices of the edges in S, where Cand Care the two components of G−S. For any vertex v∈V(C)we will use the following sets in the proof: S−(v) ={z∈N(v) :d(z,X)=d(v, X)−1}if d(v, X)≥1; N(v) ∩Xif v∈X. S=(v) = {z∈N(v) :d(z,X)=d(v, X)}. (1) Let us denote µ=max{d(v, X):v∈V(C)}. (i) Suppose that µ=0. This implies that every vertex of V(C)is an end of some edge in [X,X], that is, V(C)=X. Moreover, since Gis λ′connected there exists an edge uvin C. Note that (N(v) −u)∪(N(u)−v) ⊂X∪Xand that |(N(v) −u)∩(N(u)−v)| ≤ 1, since h≥6. If (N(v) −u)∩(N(u)−v) = ∅ then λ′(G)≥ |[v, X]| + |[(N(v) −u)∩X,X]| + |[u,X]| + |[(N(u)−v) ∩X,X]| =d(v) +d(u)−2≥ξ(G), which is a contradiction. Thus, (N(v) −u)∩(N(u)−v) = {z}yielding that u, v, zinduce a triangle in G, i.e., g=3. Observe that the sets (N(v) ∩X)\ {u,z}, (N(u)∩X)\ {v, z}, (N(z)∩X)\ {u, v}and {u, v, z}are pairwise disjoint since Ghas no cycle of length four. Therefore, λ′(G)≥ |[v, X]| + |[(N(v) ∩X)\ {u,z},X]| + |[u,X]| + |[(N(u)∩X)\ {v, z},X]| + |[z,X]| + |[(N(z)∩X)\ {u, v},X]| ≥ |N(v) \ {u,z}| + |N(u)\ {v, z}| + |N(z)\ {u, v}| ≥d(v) −2+d(u)−2+d(z)−2 =d(v) +d(u)+d(z)−6 ≥ξ(G), because by hypothesis when g=3, δ ≥3 and Ghas no triangle with all its vertices of degree 3, leading to a contradiction. Thus µ≥1 and item (i) holds. (ii) Assume by way of contradiction that 1 ≤µ≤(h−6)/2 (i.e., h≥8) let us choose a vertex u∈Nµ(X)∩V(C)such that |S−(u)|≤|S−(v)|for all v∈Nµ(X)∩V(C), and denote by δN(u)=min{d(v) :v∈N(u)}. Let us consider the sets A=N2(u)∩Nµ(X), B=N2(u)∩Nµ−1(X)and D=N2(u)\(A∪B). Note that Nµ−1(B)∩X=Bif µ=1 and |Nµ−1(B)∩X|≥|B| if µ≥2, otherwise an even cycle of length at most 2µ+2≤h−4 would be created. Also observe that |D| ≥ 1 and D⊂X if µ=1. Two cases need to be distinguished. Case 1. |S−(u)| ≥ 2, therefore |S−(v)| ≥ 2 for every v∈Nµ(X)∩V(C), due to the way uhas been chosen. C. Balbuena et al. / Applied Mathematics Letters 24 (2011) 1041–1045 1043 In particular, |Nµ(a)∩X|≥|S−(a)| ≥ 2 for all a∈A, yielding |Nµ(A)\Nµ(u)∩X|≥|A|for if not, an even cycle of length at most 2µ+4≤h−2 appears. Moreover, for the same reason, |[Nµ(u)∩X,X]| ≥ |D|. Hence, ξ(G)−1≥ |[X,X]| ≥ |[Nµ(u)∩X,X]| + |[Nµ(A)\Nµ(u)∩X,X]| ≥ |D|+|A| =(|N2(u)|−|A|−|B|)+ |A| ≥     − v∈N(u) (d(v) −1)− |B|if g≥5; − v∈N(u) (d(v) −2)− |B|if g=3.(2) If g=3 and δ≥5, from (2) it follows that d(u)+δN(u)−3≥ξ(G)−1≥− v∈N(u) (d(v) −2)− |B| ≥ d(u)(δN(u)−2)− |B|, yielding that |B| ≥ d(u)(δN(u)−2)−d(u)−δN(u)+3=(d(u)−1)(δN(u)−3). Taking into account that (a−1)(b−3)≥a+b−2 for a,b≥5 two integer numbers, we have |B| ≥ d(u)+δN(u)−2. Hence, λ′(G)≥ |X|≥|Nµ−1(B)∩X|≥|B| ≥ d(u)+δN(u)−2≥ξ(G), against the fact that Gis non-λ′-optimal. If g≥5, by hypothesis δ≥4. From (2) it follows that |B| ≥ (d(u)−1)(δN(u)−2)+1. Thus, we arrive again to contradiction by applying (a−1)(b−2)≥a+b−3 for two integers a,b≥4. Case 2. |S−(u)| = 1. Let us denote S−(u)= {w}and Aw=N(w) ∩Nµ(X), A′=A\Aw,Bw=N(w) ∩Nµ−1(X)and B′=B\Bw. Let us prove the following claim. Claim 1. |A′|+|B′| ≥ 2ξ(G)−4if g =3; 2ξ(G)−3if g ≥5. If g ≥5by hypothesis, δ≥4. Then (d(u)−1)(δN(u)−1)≤− v∈N(u)−w (d(v) −1)≤ |A′|+|B′|, yielding that |A′|+|B′| ≥ 2ξ(G)−3because ab ≥2(a+b)−3holds for any two integers a,b≥3. Furthermore, for g =3 and δ≥5, as h ≥8, we get (d(u)−1)(δN(u)−2)≤− v∈N(u)−w (d(v) −2)≤ |A′|+|B′|. Thus |A′|+|B′| ≥ 2ξ(G)−4because (a−1)(b−2)≥2(a+b−2)−4holds for any integers a,b≥5. Note that the sets Nµ(A′)∩Xand Nµ−1(w) ∩Xare disjoint, otherwise an even cycle of length at most 2µ+2≤h−4 would be created. Furthermore, by the same reason, |[Nµ(A′)∩X,X]| ≥ |Nµ(A′)∩X|≥|A′|and |[Nµ−1(w) ∩X,X]| ≥ |D|. Thus |A′|+|D| ≤ |[Nµ(A′)∩X,X]| + |[Nµ−1(w) ∩X,X]| ≤ ξ(G)−1.(3) Also, since the sets Nµ−1(B′)∩Xand Nµ−1(Bw)∩Xare pairwise disjoint, and |Nµ−1(B′)∩X|≥|B′|and |Nµ−1(Bw)∩X| ≥ |Bw|, hence |B′|+|Bw| ≤ |Nµ−1(B′)∩X|+|Nµ−1(Bw)∩X| ≤ ξ(G)−1.(4) If g≥5, from (3),(4) and Claim 1 it follows that 2ξ(G)−2≤ |A′| + 1+ |B′| ≤ |A′| + |D| + |B′| + |Bw| ≤ 2ξ(G)−2, yielding that all the above inequalities are equalities. That is, |D|+|Bw| = 1 |A′| = ξ(G)−2 |B′| = ξ(G)−1. (5) 1044 C. Balbuena et al. / Applied Mathematics Letters 24 (2011) 1041–1045 Fig. 1. Polarity graphs for q=2,3,4. If g=3, from (3),(4) and Claim 1 it follows that 2ξ(G)−3≤ |A′| + 1+ |B′|≤|A′|+|D|+|B′|+|Bw| ≤ 2ξ(G)−2, yielding that 1≤ |D|+|Bw| ≤ 2 ξ(G)−3≤ |A′| ≤ ξ(G)−2 ξ(G)−2≤ |B′| ≤ ξ(G)−1. (6) Note that Aw∪Bw∪Dis a partition of N(w) −u, and 4 ≤ |N(w) −u|=|Aw| + |Bw| + |D|=|Aw| + 2 if g=3 and δ≥5, and 3 ≤ |N(w) −u|=|Aw|+|Bw|+|D|=|Aw| + 1. Thus |Aw| ≥ 2. Note that |Aw∩N(u)| ≤ 1 because Ghas no cycles of length 4. Thus there exists a vertex aw∈Aw\N(u)such that there is z∈S=(aw)with z∈ N(u)∪ {u}. As the sets Nµ−1(B′)∩Xand Nµ(z)∩Xare disjoint, then by (5) and (6) we have ξ(G)= |B′| + 1≤ |Nµ−1(B′)∩X|+|Nµ(z)∩X| ≤ ξ(G)−1, which is a contradiction. Hence S=(aw)= ∅, and |S−(aw)| ≥ 4. This implies, as Nµ−1(S−(aw)) ∩Xand Nµ(A′)∩Xare disjoint, and applying (5) and (6), that ξ(G)≤ |A′| + 4≤ |A′|+|S−(aw)|≤|Nµ(A′)∩X|+|Nµ−1(S−(aw)) ∩X| ≤ ξ(G)−1 a contradiction, which finishes the proof.  Proof of Theorem 1.1. We will only do the proof of (ii), the proof of (i) is analogous. Suppose that Gis non-λ′-optimal and consider a λ′-cut [V(C), V(C)] = [X,X]. By Proposition 2.1, there exists a vertex u∈V(C)such that d(u,X)≥(h−4)/2 and there exists a vertex u∈V(C)such that d(X,u)≥(h−4)/2. Hence diam(G)≥d(u,X)+1+d(X,u)≥h−3, against the hypothesis diam(G)≤h−4.  One important family of graphs with girth pair g=3 and h=6 are polarity graphs defined as follows. Let Pbe a finite projective plane, and let πbe a polarity of P(a one-to-one mapping of points onto lines such that p′∈π(p) whenever p∈π(p′)). The polarity graph G(P, π) is the graph whose vertex set is the set of points of Pand whose edge set is {pp′:p∈π(p′)}. A polarity graph has diameter 2, g=3 and no 4-circuits, and they are the unique graphs satisfying these requirements [14]. Its vertex connectivity has been studied very recently in [11]. Polarity graphs are extremal graphs for the extremal problem of finding graphs with a maximum number of edges with no 4-circuits of order nwhen n=q2+q+1,q being a prime power; see [15–17]. The vertices have degrees qor q+1, the vertices lying on triangles have degree q+1 and two vertices of degree qare not adjacent. Fig. 1 depicts three polarity graphs for q=2,3,4. Theorem 2.1. Polarity graphs are λ′-optimal. Proof. It is not difficult to check that for q=2 the corresponding graph of seven vertices is λ′-optimal; see Fig. 1. Furthermore, by Theorem 1.1, polarity graphs are λ′-optimal for q≥4 (because qis the minimum degree). Finally, the polarity graph for q=3 has diameter 2 and there is no triangle with all its vertices of degree 3. Hence, by applying Proposition 2.1 this graph is also λ′-optimal.  Acknowledgements The authors would like to thank the anonymous referees for their kind help and valuable suggestions which led to an improvement of this paper. 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; also by Catalonian government 2009 SGR 1298. C. Balbuena et al. / Applied Mathematics Letters 24 (2011) 1041–1045 1045 References [1] G. Chartrand, L. Lesniak, Graphs and Digraphs, 4th ed., Chapman and Hall, London, UK, 2005. [2] A.H. Esfahanian, S.L. Hakimi, On computing a conditional edge-connectivity of a graph, Inform. Process. Lett. 27 (1988) 195–199. [3] C. Balbuena, M. Cera, A. Diánez, P. García-Vázquez, X. Marcote, Sufficient conditions for λ′-optimality of graphs with small conditional diameter, Inform. Process. Lett. 95 (2005) 429–434. [4] C. Balbuena, P. García-Vázquez, X. Marcote, Sufficient conditions for λ′-optimality in graphs with girth g, J. Graph Theory 52 (1) (2006) 73–86. [5] A. Hellwig, L. Volkmann, Sufficient conditions for graphs to be λ′-optimal, super-edge-connected, and maximally edge-connected, J. Graph Theory 48 (2005) 228–246. [6] A. Hellwig, L. Volkmann, Sufficient conditions for λ′-optimality in graphs of diameter 2, Discrete Math. 283 (2004) 113–120. [7] Z. Zhang, Sufficient conditions for restricted-edge-connectivity to be optimal, Discrete Math. 307 (22) (2007) 2891–2899. [8] F. Harary, P. Kovács, Regular graphs with given girth pair, J. Graph Theory 7 (1983) 209–218. [9] C. Balbuena, T. Jiang, Y. Lin, X. Marcote, M. Miller, Order of regular graphs with given girth pair, J. Graph Theory 55 (2007) 153–163. [10] C. Balbuena, M. Cera, A. Diánez, P. García-Vázquez, X. Marcote, Connectivity of graphs with given girth pair, Discrete Math. 307 (2007) 155–162. [11] C. Balbuena, P. García-Vázquez, L.P. Montejano, Superconnectivity of graphs with odd girth gand even girth h, Discrete Appl. Math. 159 (2–3) (2011) 91–99. [12] J. Fàbrega, M.A. Fiol, Maximally connected digraphs, J. Graph Theory 13 (3) (1989) 657–668. [13] M. Imase, T. Soneoka, K. Okada, Connectivity of regular directed graphs with small diameter, IEEE Trans. Comput. C-34 (1985) 267–273. [14] J.A. Bondy, P. Erdös, S. Fajtlowicz, Graphs of diameter two with no 4-circuits, Discrete Math. 200 (1999) 21–25. [15] M. Abreu, C. Balbuena, D. Labbate, Adjacency matrices of polarity graphs and of other C4-free graphs of large size, Des. Codes Cryptogr. 55 (2010) 221–231. [16] Z. Füredi, Graphs without quadrilaterals, J. Combin. Theory Ser. B 34 (1983) 187–190. [17] Z. Füredi, On the number of edges of quadrilateral-free graphs, J. Combin. Theory Ser. B 68 (1996) 1–6.