On the connectivity and restricted edge-connectivity of 3-arc graphs

Depósito de investigación de la Universidad de Sevilla https://idus.us.es/ Esta es la versión aceptada del artículo publicado en: This is an accepted manuscript of a paper published in: Discrete Applied Mathematics (Vol. 162): 10 January 2014 DOI: https://doi.org/10.1016/j.dam.2013.08.010 Copyright: El acceso a la versión publicada del artículo puede requerir la suscripción de la revista. Access to the published version may require subscription. “This is an Accepted Manuscript of an article published by Elsevier in Discrete Applied Mathematics on 10 January 2014, available at: https://doi.org/10.1016/j.dam.2013.08.010.” On the connectivity and restricted edge-connectivity of 3-arc graphs Camino Balbuena and Luis Pedro Montejano Universitat Polit`ecnica de Catalunya Barcelona Pedro Garc´ıa-V´azquez Universidad de Sevilla Sevilla Abstract A3−arc of a graph Gis a 4-tuple (y,a,b,x) of vertices such that both (y,a,b)and(a, b, x)arepathsoflengthtwoinG. Let ←→ Gdenote the symmetric digraph of a graph G.The3-arc graph X(G)ofagivengraphGis defined to have vertices the arcs of ←→ G. Two vertices (ay), (bx) are adjacent in X(G)ifand only if (y,a,b,x) is a 3-arc of G. The purpose of this work is to study the edge-connectivity and restricted edge-connectivity of 3-arc graphs. We prove that the 3-arc graph X(G)ofevery connected graph Gof minimum degree δ(G)≥3 has edgeconnectivity λ(X(G)) ≥(δ(G)−1)2; and restricted edgecon- nectivity λ(2)(X(G)) ≥2(δ(G)−1)2−2ifκ(G)≥2. We also provide examples showing that all these bounds are sharp. 1 Introduction Throughout this paper, only undirected simple graphs without loops or multiple edges are considered. Unless otherwise stated, we follow [10] for terminology and definitions. Let Gbe a graph with vertex set V(G)andedgesetE(G). For every v∈V(G), NG(v) denotes the neighborhood of v, that is, the set of all vertices adjacent to v.Thedegree of a vertex vis d(v)=|NG(v)|and the 79 On the connectivity and restricted edge-connectivity of 3-arc graphs C. Balbuena et al. minimum degree δ=δ(G) of the graph Gis the minimum degree over all vertices of G. AgraphGis called connected if every pair of vertices is joined by a path. If S⊂V(G)andG−Sis not connected, then Sis said to be a cutset.Acomponent of a graph Gis a maximal connected subgraph of G. A (noncomplete) connected graph is called k-connected if every cutset has cardinality at least k.Theconnectivity κ(G) of a (noncomplete) connected graph Gis defined as the maximum integer ksuch that Gis k-connected. The minimum cutsets are those having cardinality κ(G). The connectivity of a complete graph Kδ+1 on δ+ 1 vertices is defined as κ(Kδ+1)=δ. Analogously, for edge connectivity an edge-cut in a graph Gis a set W of edges of Gsuch that G−Wis nonconnected. If Wis a minimum edge-cut of a connected graph G,thenG−Wcontains exactly two components. Every connected graph on at least two vertices has an edge-cut. The edge-connectivity λ(G) of a graph Gis the minimum cardinality of an edge-cut of G. A classic result due to Whitney is that for every graph G, κ(G)≤λ(G)≤δ(G). A graph is maximally connected if κ(G)=δ(G), and maximally edge-connected if λ(G)=δ(G). Though the parameters κ, λ of connectivities give the minimum cost to disrupt the network, they do not take into account what remains after deletion. Even two graphs with the same connectivity κ, λ may be considered to have different reliabilities, since the number of minimum cutsets or edge-cuts is different. Superconnectivity is a stronger measure of connectivity, introduced by Boesch and Tindell in [8], whose study has deserved some attention in the last years, see for instance, [1, 6, 7, 19, 20]. A maximally connected [edge-connected] graph is called super-κ[super-λ]iffor every cutset [edge-cut] Wof cardinality δ(G) there exists a component C of G−Wof cardinality |V(C)|= 1. The study of super-κ[super-λ] graphs has a particular significance in the design of reliable networks, mainly due to the fact that attaining superconnectivity implies minimizing the number of minimum cutsets [edge-cuts] (see [7, 20]). In order to measure the super edge-connectivity we use the following parameter introduced by Esfahanian and Hakimi [11]. The restricted edgeconnectivity λ(2) =λ(2)(G) is the minimum cardinality over all restricted edge-cuts W, i.e., those such that there are no isolated vertices in G−W. A restricted edge-cut Wis called a λ(2)-cut if |W|=λ(2). Obviously for any λ(2)-cut W, the graph G−Wconsists of exactly two components 80 On the connectivity and restricted edge-connectivity of 3-arc graphs C. Balbuena et al. C,Cand clearly |V(C)|≥2,|V(C)|≥2. A connected graph Gis called λ(2)-connected if λ(2) exists. Esfahanian and Hakimi [11] showed that each connected graph Gof order n(G)≥4 except a star, is λ(2)-connected and satisfies λ(2) ≤ξ,whereξ=ξ(G) denotes the minimum edge-degree of G defined as ξ(G)=min{d(u)+d(v)−2:uv ∈E(G)}.Furthermore,a λ(2)-connected graph is said to be λ(2)-optimal if λ(2) =ξ. Recent results on this property are obtained in [2, 5, 12, 13, 18, 21, 23]. Notice that if λ(2) ≤δ,thenλ(2) =λ.Whenλ(2) >δ(that is to say, when every edge cut of order δisolates a vertex) the graph must be super-λ. Therefore, by means of this parameter we can say that a graph Gis super-λif and only if λ(2) >δ. Thus, we can measure the super edge-connectivity of the graph as the value of the restricted edge-connectivity λ(2). Let ←→ Gdenote the symmetric digraph of a graph G. For adjacent vertices u, v of V(G)weuse(u, v) to denote the arc from uto v,and (v,u)(=(u, v)) to denote the arc from vto u.A3-arc is a 4-tuple (y,a,b,x) of vertices such that both (y,a,b)and(a, b, x)arepathsoflengthtwoinG. The 3-arc graph X(G)ofagivengraphGis defined to have vertices the arcs of ←→ Gand they are denoted as (uv). Two vertices (ay),(bx) are adjacent in X(G) if and only if (y,a,b,x) is a 3-arc of G, see [17, 22]. Equivalently, two vertices (ax),(by) are adjacent in X(G) if and only if dG(a, b) = 1; that is, the tails a, b of the arcs (a, x),(b, y)∈A(←→ G) are at distance one in G. Thus the number of edges of X(G)isuv∈E(G)(d(u)−1)(d(v)−1) so that the minimum degree of X(G)is(δ(G)−1)2. There is a bijection between the edges of X(G) and those of the 2-path graph P2(G), which is defined to have vertices the paths of length two in Gsuch that two vertices are adjacent if and only if the union of the corresponding paths is a path or a cycle of length three, see [9]. Since P2(G) is a spanning subgraph of the second iterated line graph L2(G)=L(L(G)) (see e.g. [14]), we have a relation between 3-arc graphs and line graphs. Some results on the connectivity of P2-path graphs are studied e.g. in [3, 4, 15]. The purpose of this paper is to study the edge-connectivity, the restricted edge-connectivity and vertex-connectivity of the 3-arc graph X(G) of a given graph G. The following theorem gather together the results on connectivity of 3-arc-graph X(G) obtained by Knor and Zhou [16]. Theorem 1 [16] Let Gbe a graph with minimum degree δ(G). (i) X(G)is connected if Gis connected and δ(G)≥3. 81 On the connectivity and restricted edge-connectivity of 3-arc graphs C. Balbuena et al. (ii) κ(X(G)) ≥(κ(G)−1)2if κ(G)≥3. The main results contained in this paper are the following: Let Gbe a connected graph with minimum degree δ(G)≥3. (i) λ(X(G)) ≥(δ(G)−1)2. (ii) λ(2)(X(G)) ≥2(δ(G)−1)2−2if κ(G)≥2. (iii) κ(X(G)) ≥min{κ(G)(δ(G)−1),(δ(G)−1)2}. (iv) X(G)is super-κif κ(G)=δ(G)and δ(X(G)) = (δ(G)−1)2. 2 Results on the edge-connectivity and restricted edge-connectivity of 3-arc graphs Let X(G) be the 3-arc graph of a graph G.If(ay)and(bx)areadjacentin X(G) then the edge (ay)(bx) will be called an ab-edge (or ba-edge). Observe that (ay)(bx)=(bx)(ay) but (ay)=(ya)and(bx)=(xb). For any edge ab ∈E(G)letVa ab ={(ay)∈V(X(G)) : y∈NG(a)−b}. Observe that the induced subgraph of X(G)bythesetVa ab ∪Vb ba is the complete bipartite graph K|Va ab|,|Vb ba|=Kd(a)−1,d(b)−1. If Wis a minimal edge cut of a connected graph G, then, G−Wnecessarily contains exactly two components Cand C, so it is usual to denote an edge cut Was [C, C]where[C, C] denotes the set of edges between C and its complement C. Lemma 2 Let Gbe a graph and [C, C]an edge-cut of X(G).Letab ∈ E(G),if[C, C]contains ab-edges, then it contains at least min{d(a)− 1,d(b)−1}ab-edges. Proof: Suppose that (ay)(bx)isanedgeof[C, C] such that (ay)∈V(C) and (bx)∈V(C). Then Va ab ∩V(C)=∅and Vb ba ∩V(C)=∅. Let denote by |Va ab ∩V(C)|=ra≥1, |Vb ba ∩V(C)|=rb≥0, |Va ab ∩V(C)|=ra≥0and |Vb ba ∩V(C)|=rb≥1. Moreover, these numbers must satisfy ra+ra= d(a)−1andrb+rb=d(b)−1. Furthermore, the number of ab-edges contained in [C, C]israrb+rbra,thatis, |[C,C]|≥rarb+rbra.(1) 82 On the connectivity and restricted edge-connectivity of 3-arc graphs C. Balbuena et al. If rb=0,thenrb=d(b)−1. As ra≥1, (1) implies |[C, C]|≥d(b)−1and the lemma follows. Similarly, if ra= 0, the result is also true. Therefore, we can assume that ra,r b, ra, rb≥1. In this case rarb+rbra≥ra+ra=d(a)−1, and rarb+rbra≥rb+rb=d(b)−1, and the result holds.  Suppose that [C, C] is an edge-cut of X(G). Let denote by ω(α)={e∈ E(G):e=αβ}and define A={αβ ∈E(G):(αy)(βx)∈[C, C]}. Then, as a consequence of the above lemma, we have |[C, C]|≥|A|(δ(G)−1). Next we prove that |[C, C]|≥(δ(G)−1)2. Lemma 3 Let Gbe a graph and [C, C]an edge-cut of X(G).Letab ∈ E(G)and suppose that ab ∈A.Then|(ω(a)∪ω(b)) ∩A|≥(δ−1)2. Proof: Suppose that for all y∈N(a)−b,ay ∈A. Then there are at least δdifferent ay-edges in [C,C], and by Lemma 2 the number of ayedges in [C, C]isatleastδ(δ−1) >(δ−1)2. The same occurs if for every x∈N(b)−a,bx ∈A. Therefore we may assume that there exists y0∈NG(a)−bsuch that ay0∈Aand there exists x0∈NG(b)−asuch that bx0∈A. As ab ∈A,(ay)(bx)∈[C, C]forsomey∈N(a)−band x∈N(b)−a, and without loss of generality we may suppose that (ay)∈V(C), (bx)∈ V(C). Suppose that (ay0)(bx0)∈ [C,C]. Without loss of generality we may assume that (ay0),(bx0)∈V(C)inwhichcase(ay)(bx0)∈[C,C] because (ay)∈V(C). Then we can continue the proof assuming that there is an edge (ay)(bx)∈[C,C] such that bx ∈A, i.e., there are no bx-edges in [C,C]. First suppose that Vx xb ∩V(C)=∅.LetB={x∈NG(b)\{x, a}: (xz)∈V(C)}and B={x∈NG(b)\{x, a}:(xz)∈V(C)}.Observe that for all x∈B∪B,(xz)isadjacentto(bx)∈V(C), and (xz)is adjacent to (ba). Hence the edge-cut [C, C]mustcontain|B|different bx- edges. Moreover, since (ba) is adjacent to every (xb)∈V x xb and bx ∈A, then (ba)∈V(C) because our assumption Vx xb ∩V(C)=∅. Hence [C, C] also contains |B|different bx-edges yielding that [C, C]containsatleast |B|+|B|+|{ab}| =d(b)−1≥δ−1 different bv-edges with v∈N(b)and by Lemma 2, the result holds. Second suppose that Vx xb ⊂V(C). Hence Vb ba ⊂V(C) because every (bx)∈V b ba is adjacent to every (xb)∈V x xb and [C, C] does not contain bx-edges. If ay ∈A, reasoning for ay inthesamewayasforbx we get that Va ab ⊂V(C). Thus as Vb ba ⊂V(C) it follows that [C,C]containsatleast 83 On the connectivity and restricted edge-connectivity of 3-arc graphs C. Balbuena et al. (d(a)−1)(d(b)−1) ≥(δ−1)2ab-edges and the lemma holds. Therefore, suppose that ay ∈A. We know that there exists v∈NG(a)−ysuch that av ∈A.As(va) is adjacent to (ay) for all (va)∈Vv va it follows that Vv va ⊂V(C) (because (ay)∈V(C)andav ∈A). Hence Va av ⊂V(C) because every (ay)∈Va av is adjacent to (va)∈Vv va.AsVb ba ⊂V(C) it follows that [C,C]containsat least (d(a)−2)(d(b)−1) ab-edges. Further, as ay ∈A, by Lemma 2, [C, C] also contains at least δ−1ay-edges, yielding that the number of au-edges contained |[C,C]|is at least (δ−2)(δ−1) + (δ−1) = (δ−1)2,andthe lemma holds.  Theorem 4 Let Gbe a connected graph with minimum degree δ≥3.Then λ(X(G)) ≥(δ−1)2. Proof: Let [C,C] be a minimum edge-cut of X(G)andA={ab ∈E(G): (ay)(bx)∈[C,C]}.AsGis connected and δ≥3, then X(G) is connected yielding that |A| ≥ 1. So considering ab ∈A, and using Lemma 3 we get |[C,C]|≥(δ−1)2, following the theorem.  The following corollary is an immediate consequence from Theorem 4, and from the fact that if Gis a graph of minimum degree δhaving an edge xy such that d(x)=δand d(y)=δfor all y∈NG(x)−y, then the minimum degree of X(G)isδ(X(G)) = (δ−1)2. Corollary 5 Let Gbe a connected graph of minimum degree δ≥3having an edge xy such that d(x)=δand d(y)=δfor all y∈NG(x)−y.Then the 3-arc graph X(G)of Gis maximally edge-connected. Figure 1 shows a 3-regular graph Gwith λ(G) = 1 and its 3-arc graph X(G) which has λ(X(G)) = 4 = δ(X(G)). However X(G)isnotsuper-λ and hence is not λ(2)-optimal. And Figure 2 shows a 3-regular graph Gwith λ(G)=κ(G) = 2, and its 3-arc graph X(G) which has λ(X(G)) = 4 and λ(2)(X(G)) = 6 = ξ(X(G)), i.e., this graph is λ(2)-optimal. In what follows we give a lower bound on the restricted edge-connectivity λ(2)(X(G)) where Gis a graph having connectivity κ(G)≥2. Two edges which are incident with a common vertex are adjacent. 84 On the connectivity and restricted edge-connectivity of 3-arc graphs C. Balbuena et al. Figure 1: A 3-regular graph with λ= 1 and its 3-arc graph. Figure 2: A 3-regular graph with λ=2(κ= 2) and its 3-arc graph. Lemma 6 Let Gbe a graph with minimum degree δ≥3and vertex connectivity κ≥2.Let[C,C]be a restricted edge-cut of X(G)and consider the set A={ab ∈E(G):(ay)(bx)∈[C, C]}. Then there are at least two nonadjacent edges in A. Proof: Clearly A =∅, because X(G) is connected. Thus let (ay)∈V(C) and (bx)∈V(C) be two adjacent vertices in X(G), which implies that ab ∈A.Since[C, C] is a restricted edge-cut, then there exist (uy)∈V(C) and (wx)∈V(C)adjacentto(ay)and(bx)inX(G), respectively. Observe that we may assume that u=wbecause δ≥3. Since Gis 2-connected we can find a path R:u=r0,r 1,...,r k=wfrom uto win G−a.Asδ≥3, there exists vi∈N(ri)\{ri−1,r i+1}for each i=1,...,k −1. Moreover 85 On the connectivity and restricted edge-connectivity of 3-arc graphs C. Balbuena et al. we may choose v0=yand vk=x. Then the path Rinduces in X(G) the path R∗:(uy),(r1v1),...,(rk−1vk−1),(wx)(observethatifk=1 then R∗:(uy),(wx)). Since (uy)∈V(C)and(wx)∈V(C), it follows that [C, C]∩E(R∗)=∅, hence riri+1 ∈Afor some i∈{0,...,k}.Since a∈ V(R)thena∈{ri,r i+1}. Now reasoning analogously, we can find a path S:u=s0,s 1,...,s = wfrom uto win G−bthat induces a path S∗from (uy)∈V(C)to (wx)∈V(C). This implies that [C, C]∩E(S∗)=∅, hence sjsj+1 ∈Afor some j∈{0,...,}.Sinceb∈ V(S)thenb∈{sj,s j+1}. As ab, riri+1,s jsj+1 ∈A,a∈{ri,r i+1}and b∈{sj,s j+1}, it follow that al least two of the edges of {ab, riri+1,s jsj+1}are nonadjacent.  Theorem 7 Let Gbe a graph with minimum degree δ≥3and vertex connectivity κ≥2.ThenX(G)has restricted edge-connectivity λ(2)(X(G)) ≥ 2(δ−1)2−2. Proof: Let [C,C] be a restricted edge-cut of X(G) and consider the set A={ab ∈E(G):(ay)(bx)∈[C, C]}. From Lemma 6, Acontains two nonadjacent edges ab and cd. By Lemma 3, the number of au-edges and bv-edges, u, v ∈N(a)∪N(b) contained in [C,C]isatleast(δ−1)2,and the number of cu-edges and dv-edges, u, v ∈N(c)∪N(d) contained in [C,C]isatleast(δ−1)2.If|[{a, b},{c, d}]∩A|≤2then|[C, C]|≥2(δ− 1)2−|[{a, b},{c, d}]∩A|≥2(δ−1)2−2. If 3 ≤|[{a, b},{c, d}]∩A|≤4 then we may assume without loss of generality that ac, bd ∈A, hence, by applying Lemma 3, the number of au-edges and cv-edges, u, v ∈N(a)∪N(c) contained in [C,C]isatleast(δ−1)2, and the number of bu-edges and dvedges, u, v ∈N(b)∪N(d) contained in [C, C]isatleast(δ−1)2.Thus, |[C,C]|≥2(δ−1)2−|[{a, b},{c, d}]∩A|+2(δ−1)2−|[{a, c},{b, d}]∩A| ≥4(δ−1)2−8 ≥2(δ−1)2−2, since δ≥3. Hence the theorem is valid.  Figure 3 shows that λ(G)≥2 is not enough to guarantee that λ(2)(X(G)) ≥ 2(δ−1)2−2. In this example Gis a 4-regular graph with λ=2andκ=1, but λ(2)(X(G)) = 12 <16. The following corollary is an immediate consequence from Theorem 7, and from the fact that if Gis graph of minimum degree δhaving an edge 86