A sufficient condition for P-k-path graphs being r-connec

A sufficient condition for Pk-path graphs being r-connected夡 C. Balbuenaa, P. García-Vázquezb aDepartament de Matemàtica Aplicada III, Universitat Politècnica de Catalunya, Campus Nord, Edifici C2,C/Jordi Girona1i3, E-08034 Barcelona, Spain bDepartamento de Matemática Aplicada I, Universidad de Sevilla, Avda Reina Mercedes 2, E-41012 Sevilla, Spain Abstract Given an integer k ⩾1 and any graph G, the path graph Pk(G) has for vertices the paths of length k in G, and two vertices are joined by an edge if and only if the intersection of the corresponding paths forms a path of length k − 1in G, and their union forms either a cycle or a path of length k + 1. Path graphs were investigated by Broersma and Hoede [Path graphs, J. Graph Theory 13 (1989), 427–444] as a natural generalization of line graphs. In fact, P1(G) is the line graph of G.For k = 1, 2 results on connectivity of Pk(G) have been given for several authors. In this work, we present a sufficient condition to guarantee that Pk(G) is connected for k ⩾2 if the girth of G is at least (k + 3)/2 and its minimum degree is at least 4. Furthermore, we determine a lower bound of the vertex-connectivity of Pk(G) if the girth is at least k + 1 and the minimum degree is at least r + 1 where r ⩾2 is an integer. Keywords: Connectivity; r-connected; Path graphs 1. Introduction Throughout this paper only undirected simple graphs without loops or multiple edges are considered. Unless stated otherwise, we follow the book by Chartrand and Lesniak [6] for terminology and definitions. A graph Gis said to be connected if any two vertices can be joined by a path. A graph Gis r-connected (r⩾2) if either Gis a complete graph Kr+1or else it has at least r+2 vertices and no set of r−1 vertices separates it. The aim of this paper is to study the connectivity of Pk-path graphs. Following the notation that Knor and Niepel used in [9], given a positive integer kand a graph G, the vertex set of the Pk-path graph Pk(G) is the set of all paths of length kof G, two vertices of Pk(G) are joined by an edge if and only if the intersection of the corresponding paths forms a path of length k−1inG, and their union forms either a cycle or a path of length k+1. This means that the vertices are adjacent if and only if one can be obtained from the other by “shifting” the corresponding paths in G.Itis worth mentioning that path graphs are very related to sequence graphs defined by Fiol et al. [8]. Instead of considering the paths of Gof length kas vertices, these authors consider the walks of G(not necessarily different vertices) of length k, the adjacency being the same. 夡Research supported by the Ministry of Education and Science, Spain, and the European Regional Development Fund (ERDF) under project MTM2005-08990-C02-02. E-mail addresses: [email protected] (C. Balbuena), [email protected] (P. García-Vázquez). doi:10.1016/j.dam.2007.04.003 1746 C. Balbuena, P. García-Vázquez / Discrete Applied Mathematics 155 (2007) 1745–1751 Path graphs were introduced by Broersma and Hoede [5] as a natural generalization of line graphs, because for k=1 path graphs are just line graphs. Since then, most of the work carried out focused in case k=2. Thus, Broersma and Hoede [5] characterized the graphs that are P2-path graphs; a problem with their characterization was resolved by Li and Lin [14]. The determination problem for P2-path graphs is solved in [1,16–18], and distance properties of path graphs are studied in [4,11]. Results on the edge-connectivity of line graphs are given by Chartrand and Stewart [7], later by Zamfirescu [20], and recently by Meng [19]. Recent results on vertex-connectivity of iterated line graphs are provided by Knor and Niepel [12]. The vertex-connectivity of P2-path graphs has been studied by Knor et al. [13] and by Li [15]. From a result showed in [11], it is not difficult to see that if Gis a connected graph with at most one vertex of degree one, then P2(G) is also connected. In [2] the edge-connectivity of P2-graphs is studied giving lower bounds on the edge-connectivity which are expressed in terms of the edge-connectivity of G. These latter bounds are generalized in [3] for k⩾2. Recently, Knor and Niepel [10] have studied the connectivity of P3-path graphs, and furthermore the following sufficient condition to guarantee connected Pk-path graphs for k⩾2 is easily derived. Theorem A (Knor and Niepel [10]).Let k⩾2be an integer. Let G be a connected graph of minimum degree (G)⩾2 and girth g(G)⩾k+1. Then Pk(G) is connected. In this work, we show that the condition on the girth of Theorem A can be relaxed if the minimum degree is at least 4. Furthermore, we determine a lower bound of the vertex-connectivity of Pk(G) if the girth is at least k+1 and the minimum degree is at least r+1 where r⩾2 is an integer. More precisely we prove the following two theorems. Theorem 1.1. Let k⩾2be an integer.Let G be a connected graph of minimum degree (G)⩾4and girth g(G)⩾ (k +3)/2.Then Pk(G) is connected. Theorem 1.2. Let k, r ⩾2be integers.LetGbeanr-connected graph of minimum degree (G)⩾r+1and girth g(G)⩾k+1. Then Pk(G) is r-connected. Notice that Theorem 1.2 can be seen as a generalization of Theorem A, because for r=1 Theorem 1.2 is just Theorem A. 2. Proofs Let us consider a positive integer k⩾2. Let us denote by U=(u0u1···uk)a vertex in Pk(G), and by U:u0,u 1,...,u k the corresponding path of length kin G. We would like to emphasize that ui= ujfor every pair of vertices included in U, and that U=(u0u1···uk)=(ukuk−1···u0). Lemma 1. Let k⩾2be an integer. Let G be a connected graph of minimum degree (G)⩾4and girth g(G)⩾(k + 3)/2.Suppose that U=(u0u1···uk)and V=(v0v1···vk)are two vertices in Pk(G) such that uk=vk.Then there exists a path from U to V in Pk(G). Proof. Let ibe the smaller integer in {1,2,...,k}such that ul=vlfor l=i,...,k. See Fig. 1. Notice that it could exist some s,l ∈{0,...,i−1}in such a way that {u0,...,u s}∩{v0,...,v l} =∅, see Fig. 2. v0v1vi-1 u0u1uk = vk ui = vi Fig. 1. Two paths in Gdefining two vertices Uand Vin Pk(G) with uk=vk. C. Balbuena, P. García-Vázquez / Discrete Applied Mathematics 155 (2007) 1745–1751 1747 ui-1 u0u1 vi-1 vl-1 us = vl us-q = vl-q vl-q-1 v1 v0 ui = viuk = vk Fig. 2. Two paths in Gdefining two vertices Uand Vin Pk(G) with uk=vk. First of all, let us see that the graph Gcontains a path uk=t0,t 1,...,t isuch that tj/∈{uj,u j+1,...,u k}∪ {vj,v j+1,...,v k}for all j=1,2,...,i. If k=2,3 the lemma is clear because (G)⩾4. Thus assume k⩾4. We reason by contradiction assuming that there exists some j∈{1,2,...,i}such that each neighbor zof tj−1satisfies z∈{uj,u j+1,...,u k}∪{vj,v j+1,...,v k}. Since g(G)⩾(k +3)/2it follows that NG(tj−1)⊆{tj−2}∪{uj,...,u j+(k−3)/2}∪{vj,...,v j+(k−3)/2}. Since (G)⩾4, we may suppose that there are at least two vertices in {uj,...,u j+(k−3)/2}adjacent to tj−1. This means that Gcontains a cycle of length at most (k +1)/2against the assumption g(G)⩾(k +3)/2. Therefore, there exists a vertex tj∈NG(tj−1)such that tj/∈{uj,u j+1,...,u k}∪{vj,v j+1,...,v k}. As a consequence of the above fact we can find in Pk(G) the following path: Z:U=(u0···uk−1t0), (u1···uk−1t0t1),..., (ui···uk−1t0t1···ti)=(vi···vk−1t0t1···ti), (vi−1···vk−1t0t1···ti−1),..., (v0···vk−1t0)=(v0···vk−1vk)=V. Since the path Zjoins vertex Uwith vertex Vin Pk(G) the lemma follows.  Proof of Theorem 1.1. Given two vertices A=(a0a1···ak)and B=(b0b1···bk)of Pk(G) we will show that Aand Bcan be joined by a path in Pk(G). We distinguish two cases: Case 1: Suppose that {a0,...,a k}∩{b0,...,b k} =∅. We may assume that as=bifor some s, i ∈{0,...,k}such that if s<kthen {b0,...,b k}∩{as+1,...,a k}=∅. Let r,0⩽r⩽s, be the maximum integer such that: as−j=bi+jfor each j=0,...,r, see Fig. 3. That is, we have {bi+r+1,...,b k}∩{as−r,...,a k}=∅ and {b0,...,b i}∩{a0,...,a s}=∅. (1) Notice that it might be {bi+r+1,...,b k}∩{a0,...,a s−r−1} =∅, see Fig. 4. First suppose i+s⩽k. Then the walk w0,w 1,...,w n=bk,...,b i+r+1,a s−r,...,a s,...,a k is a path because of (1), of length n=2k−(i +s)⩾k. Applying Lemma 1 to vertices A=(a0a1···ak)and V1= (wn−k···wn)=(bi+sbi+s−1···bi+r+1as−r···ak)we can consider in Pk(G) a path Z1joining Awith V1. Moreover, since n⩾kwe can find in Pk(G) the path Z2:V1=(wn−k···wn),...,(w 0···wk)=(bk···bi+r+1as−r···as+i)=V2. 1748 C. Balbuena, P. García-Vázquez / Discrete Applied Mathematics 155 (2007) 1745–1751 a0a1as-r = bi+r bi+r+1 bk as = biak-1 ak bi-1 b1 b0 Fig. 3. Detail of paths of Gcorresponding to vertices Aand Bof Pk(G). b0 b1 bi-1 as = biak as-r = bi+r bi+r+1 bl-1 aj = bl aj-q = bl+q a0 bl+q+1 bk Fig. 4. Detail of paths of Gcorresponding to vertices Aand Bof Pk(G). Notice that if n=kthen V1=V2and Z2is a path of length zero. Finally, by applying Lemma 1 to two vertices V2=(wk···w0)=(as+i···as−rbi+r+1···bk)and B=(b0b1···bk)we obtain that there exists other path Z3joining these two vertices V2and B. Therefore, the walk Z1∪Z2∪Z3connects the vertices Aand Bin Pk(G), hence the theorem holds. Second, suppose i+s>k. Then the walk w0,w 1,...,w n=a0,...,a s−1,b i,...,b 0 is a path because of (1) of length n=i+s>k.Applying Lemma 1 to vertices B=(bkb1···b0)and V1=(wn−k···wn)= (as−(k−i) ···as−1bi···b0)we can consider in Pk(G) a path Z1joining Bwith V1. Moreover, since n>k we can find in Pk(G) the path Z2:V1=(wn−k···wn),...,(w 0···wk)=(a0···as−1bi···bi−(k−s))=V2. Finally, by applying Lemma 1 to two vertices V2=(wk···w0)=(bi−(k−s) ···bias−1···a0)and A=(akak−1···a0) we get that there exists other path Z3joining these two vertices V2and A. Therefore, the walk Z1∪Z2∪Z3connects the vertices Band Ain Pk(G), and the theorem holds. Case 2: {a0,...,a k}∩{b0,...,b k}=∅. Since Gis a connected graph, there exists in Ga path Z:al=z0,z 1,...,z h=bk, C. Balbuena, P. García-Vázquez / Discrete Applied Mathematics 155 (2007) 1745–1751 1749 b0b1 a0a1 zr = bibk-1 ak ak-1 bk z1 zr-1 z0 = al Fig. 5. Detail of disjoint paths of Gcorresponding to vertices Aand Bin Pk(G). joining al(l∈{0,...,k}) with bkin such a way {z1,...,z h}∩{a0,...,a k}=∅. Let zr=biwith r⩾1 and i∈{0,...,k} be such that {z0,...,z r−1}∩{b0,...,b k}=∅, see Fig. 5. Notice that we may assume l+i−r⩽k, because otherwise it is enough to interchange awith ak−or bwith bk−or both. Then the walk w0,...,w n=ak,...,a l,z 1,...,z r,b i+1,...,b k is in fact a path of Gof length n=2k+r−l−i⩾k. By applying Lemma 1 to vertices A=(a0a1···ak)and W1=(wk···w0)=(wk···al···ak)there exists in Pk(G) a path Z1joining Awith W1. Moreover, since n⩾kwe can find in Pk(G) the path Z2:W1=(wk···al···ak), (wk+1···al···ak−1),...,(w n···wn−k)=W2. Observe that if n=kthen W1=W2and Z2is of length 0. Finally, by applying Lemma 1 to vertices W2=(wn−k···wn)= (wn−k···bi···bk)and B=(b0b1···bk)there exists other path Z3joining these two vertices W2and B. Consequently, the walk Z1∪Z2∪Z3connects the vertices Aand Bin Pk(G), and the theorem holds.  Proof of Theorem 1.2. In order to prove the result we apply Menger’s Theorem, i.e., given two vertices of Pk(G), say A=(a0···ak)and B=(b0···bk), we will show that there exist rinternally vertex-disjoint paths in Pk(G) joining A with B. Since bk= b0we may assume that ak= bk.AsGis r-connected, by applying Menger’s Theorem, there exist r internally vertex-disjoint paths in Gconnecting akwith bk. Let us denote these paths by Zi:ak=zi 0,z i 1,...,z i hi=bkfor i=1,...,r. First, let us find r−2 internally vertex-disjoint paths in Pk(G) joining Awith B. Since the paths Ziare internally vertex-disjoint we have zi 1= ak−1and zi hi−1= bk−1for i=1,...,r −2. Moreover, due to g(G)⩾k+1wehave zi j/∈{aj,a j+1,...,a k}for 1⩽j⩽min{hi,k},i=1,...,r −2. (2) zi hi−j/∈{bj,b j+1,...,b k}for 1⩽j⩽min{hi,k},i=1,...,r −2. (3) 1750 C. Balbuena, P. García-Vázquez / Discrete Applied Mathematics 155 (2007) 1745–1751 Let us consider the walks Pi:a0,a 1,...,a k,z i 1,...,z i hi−1,b k,b k−1,...,b 0,i=1,...,r −2, and notice that if hi⩽k, then bk−j/∈{ahi+j,...,a k}for 0⩽j⩽k−hi. Otherwise the subwalk ahi+j,...,a k, zi 1,...,z i hi−1,bk,b k−1,...,b k−jcontains a cycle of length at most k < g(G), which is a contradiction. This fact together with (2) and (3) allows to find a path from Ato Bin Pk(G) by “shifting” all subwalks of length kof Pstarting in A. Since the paths Ziare internally vertex-disjoint in G, it is evident that the corresponding induced paths Z∗ iin Pk(G) are internally vertex-disjoint in Pk(G). As regards Zr−1and Zrthere are two cases to distinguish: Case (a): Suppose that zr 1=ak−1and zr hr−1=bk−1. Then zr−1 1= ak−1and zr−1 hr−1−1= bk−1and therefore, the walk Pr−1induces a new internally vertex-disjoint path in Z∗ r−1in Pk(G). Thus it remains to find a path Z∗ rin Pk(G) joining Awith Binternally vertex-disjoint with Z∗ ifor each i∈{1,...,r −1}. Since g(G)⩾k+1, it follows that for each j∈{1,2,...,k}there exist two paths ak=t0,t 1,...,t j, and bk= t∗ 0,t∗ 1,...,t∗ jsuch that tj/∈{aj,...,a k}and t∗ j/∈{bj,...,b k}. In fact, we can take these paths in such a way that t1/∈{z1 1,...,z r−1 1}and t∗ 1/∈{z1 h1−1,...,z r−1 hr−1−1},because (G)⩾r+1. Let us consider the walk wr 0,w r 1,...,w r nr=tk−1,...,t 0,z r 1,...,z r hr,t∗ 1,...,t∗ k−1 of length nr=2k−2+hr. We can find in Pk(G) the following walk connecting Awith B: Z∗ r:A=(a0a1···ak), (a1···akt1),...,(a k−1akt1···tk−1)=(wr k···wr 0), (wr k+1···wr 1),...,(w r nr−k···wr nr)=(bk−1bkt∗ 1···t∗ k−1), (bk−2bk−1bkt∗ 1···t∗ k−2),...,(b 0···bk)=B. Moreover, since Zris internally vertex-disjoint with Ziin Gand besides t1= zi 1and t∗ 1= zi h−1for all i=1,...,r−1, we deduce that Z∗ ris internally vertex-disjoint with Z∗ i,for all i=1,...,r −1. Case (b): Suppose that zr 1=ak−1and zr hr−1= bk−1,and that zr−1 1= ak−1and zr−1 hr−1−1=bk−1. As g(G)⩾k+1 there exist two paths: ak=t0,t 1,...,t k−1,and bk=t∗ 0,t∗ 1,...,t∗ k−1such that tj/∈{aj,...,a k}and t∗ j/∈{bj,...,b k},for each j∈{1,2,...,k−1}. (4) Moreover, we can take these paths in such a way that t1/∈{z1 1,...,z r−1 1}and t∗ 1/∈{z1 h1−1,...,z r hr−1}because (G)⩾ r+1. First we will construct the path Z∗ r. Let us consider the walk formed by the union of the paths {tk−1,...,t 0},{zr 0,...,z r hr}and {bk,...,b 0}, denoted by wr 0,w r 1,...,w r nr, thus nr=2k−1+hr. We can construct in Pk(G) the following walk connecting Awith B: Z∗ r:A=(a0a1···ak), (a1···akt1),...,(a k−1akt1···tk−1)=(wr k···wr 0), (wr k+1···wr 1),...,(w r nr−k···wr nr)=(bk···b0)=B. Notice that Zris internally vertex-disjoint in Gwith the paths Ziand t1= zi 1,for i=1,...,r−1. Thus Z∗ ris internally vertex-disjoint in Pk(G) with the paths Z∗ i. To construct a path Z∗ r−1we proceed in an analogous way to find the path Z∗ rchanging Awith B. Acknowledgment The authors wish to thank the referees for their helpful comments and suggestions which have allowed to improve the presentation of the paper. C. Balbuena, P. García-Vázquez / Discrete Applied Mathematics 155 (2007) 1745–1751 1751 References [1] R.E.L. Aldred, M.N. Ellingham, R.L. Hemminger, P. Jipsen, P3-isomorphisms for graphs, J. Graph Theory 26/1 (1997) 35–51. [2] C. Balbuena, D. Ferrero, Edge-connectivity and super edge-connectivity of P2-path graphs, Discrete Math. 269 (2003) 13–20. [3] C. Balbuena, P. García-Vázquez, Edge-connectivity in Pk-path graphs, Discrete Math. 286 (2004) 213–218. [4] A. Belan, P. Jurica, Diameter in path graphs, Acta Math. Univ. Comenian LXVIII (2) (1999) 111–126. [5] H.J. Broersma, C. Hoede, Path graphs, J. Graph Theory 13 (1989) 427–444. [6] G. Chartrand, L. Lesniak, Graphs and Digraphs, third ed., Chapman & Hall, London, UK, 1996. [7] G. Chartrand, J. Stewart, The connectivity of line-graphs, Math. Ann. 182 (1969) 170–174. [8] M.A. Fiol, J.L.A. Yebra, J. Fabrega, Sequence graphs and interconnection networks, Ars Combin. 16-A (1983) 7–13. [9] M. Knor, L. Niepel, Path, trail and walk graphs, Acta Math. Univ. Comenian. LXVIII (2) (1999) 253–256. [10] M. Knor, L. Niepel, Connectivity of path graphs, Discuss. Math. Graph Theory 20 (2000) 181–195. [11] M. Knor, L. Niepel, Diameter in iterated path graphs, Discrete Math. 233 (2001) 151–161. [12] M. Knor, L. Niepel, Connectivity of iterated line graphs, Discrete Appl. Math. 125 (2003) 255–266. [13] M. Knor, L. Niepel, M. Mallah, Connectivity of path graphs, Australas. J. Combin. 25 (2002) 174–184. [14] H. Li, Y. Lin, On the characterization of path graphs, J. Graph Theory 17 (1993) 463–466. [15] X. Li, The connectivity of path graphs, Combinatorics, Graph Theory, Algorithms and Applications, Beijing, 1993, pp. 187–192. [16] X. Li, On the determination problem for P3-transformation of graphs, Combinatorics and Graph Theory, vol. 1, Hefei, 1995, pp. 236–243. [17] X. Li, On the determination problem for P3-transformation of graphs, Ars Combin. 49 (1998) 296–302. [18] X. Li, Z. Biao, Isomorphisms of P4-graphs, Australas. J. Combin. 15 (1997) 135–143. [19] J. Meng, Connectivity and super edge-connectivity of line graphs, Graph Theory Notes of New York, vol. XL, 2001, pp. 12–14. [20] T. Zamfirescu, On the line-connectivity of line-graphs, Math. Ann. 187 (1970) 305–309.