Bi-super-connected digraphs

LIJing-jing,LIU Juan

(College of Mathematics Sciences,Xinjiang Normal University, Urumqi 830054,China)

Bi-super-connected digraphs

LIJing-jing,LIU Juan

(College of Mathematics Sciences,Xinjiang Normal University, Urumqi 830054,China)

A simple digraph D(without loops and multiple arcs)is said to be super connected if every minimum vertex-cut is the out-neighbor set or in-neighbor set of a vertex. A super-connected digraph D is said to be bi-super-connected if there exists a minimum vertex-cut is both the out-neighbor set of a vertex and the in-neighbor set of a vertex. In this paper,we will give the necessary and sufficient conditions of line digraph is bisuper-connected,furthermore,we study the bi-super-connectivity of Cartesian product and lexicographic product of two digraphs.

combinatorial problem s;super-connected;bi-super-connected;line digraphs;Cartesian product

0 Introduction

Let D=(V(D),A(D))be a sim p le digraph.The connectivity κ(D)is the minimum cardinality of all Vertex-cuts of digraph D.It is well know that κ(D)≤δ(D),whereδ(D)=m in{δ+(D),δ-(D)}is the minimum degree of D(δ+(D)andδ-(D)are the minimum out degree and the minimum in-degree).Hence,a digraph D is said to be maximally connected ifκ(D)=δ(D).A strongly connected digraph D is said to be super-connected,or super-κfor short,if there exists a Vertex x such that U=N+(x)or N-(x)for any minimum Vertex-cut U,where N+(x)and N-(x)are out-neighbor set and in-neighbor set of a Vertex x in D.If d+(x)=d-(x)=d for each Vertex x∈V,then D isa d-regular digraph.denotes a directed cycle of length of n.denotes a complete digraph of order n.The reverse digraph of D is the digraph D(r)=(V,{(x,y)|(y,x)∈A}),D is a symmetric digraph if A=A(r).The line digraph of D,denoted by L(D),is the digraph With Vertex set V(L(D))={aij|aij=(xi,xj)∈A(D)}, and a Vertex aijis adjacent to a Vertex astin L(D)if and only if xj=xsin D.

Let D1=(V1,A1)and D2=(V2,A2)be two digraphs,where V1={x1,x2,···,xn1}and V2={y1,y2,···,yn2}.The Cartesian product D1□D2of D1and D2has Vertex set V1×V2and((x1,y1),(x2,y2))∈A(D1□D2)if and only if either(x1,x2)∈A1and y1=y2,or x1=x2and(y1,y2)∈A2.The lexicographic product D1［D2］of D1and D2has Vertex set V1×V2and ((x1,y1),(x2,y2))∈A(D1［D2］)if and only if either(x1,x2)∈A1,or x1=x2and(y1,y2)∈A2. Let S1,S2,···,Sn1-1and Sn1be n1digraphs.The digraph D1［S1,S2,···,Sn1］is the digraph obtained from D1by replacing the i th Vertex of D1by a copy of the digraph Si,in such a way that for every arc(xi,xj)in D1,D1［S1,S2,···,Sn1］contains all possible arcs from V(Si)to V(Sj).In［1］,the authors introduced the definition of bi-super-connected,in this paper,we study the bi-super-connectivity of line digraph,Cartesian product and lexicographic product of two digraphs.

Definition 1［1］A super-connected digraph D is said to be bi-super-connected,iƒthere exist a minimum vertex-cut U such that U=N+(x)=N-(y)ƒor x,y∈V(D).

Bi-super-connected digraphs are super-connected and super-connected symmetric digraphs are bi-super-connected.If D is a bi-super-connected digraph,thenδ+(D)=δ-(D).

The study on connectivity of the Cartesian product can be found in［2-3］,where the lower bounds of the connectivity of two graphs and some sufficient conditions for it to be maximally or super-connected are giVen.In［4-6］,the authors discussed the connectivity of line graphs(digraphs).Shieh［7］determined the super-connected and super-edge-connected Cartesian product of two regular graphs.Liu and Meng［8］searched the super-connected and super-arc-connected Cartesian product of digraphs.In［9］,the authors studied the double-super-connected of line digraph and Cartesian product and lexicographic product of two digraphs.In this paper,we w ill giVe the necessary and sufficient conditions of line digraph is bi-super-connected,furthermore,we study the bi-super-connectivity of Cartesian product and lexicographic product of two digraphs.

1 Operations on digraphs

Firstly,we giVe the characterization of the bi-super-connected line digraphs.

Lemma 2［10］Let D be a digraph,thenλ(D)=κ(L(D)).

Theorem 3 Let D=(V,A)be a simple digraph,then L(D)is bi-super-connected iƒandonly iƒλ(D)=1 and there exists a cut-arc(xi,xj)∈A satisfies that d+(xi)=d-(xj)=1 in D.

P roof Ifλ(D)=1,thenκ(L(D))=1 by Lemma 2.There is a cut-Vertex aijin L(D), aij=(xi,xj)∈A(D)is a cut-arc in D,if it satisfies that d+(xi)=d-(xj)=1,then there exist two Vertices asi=(xs,xi),ajt=(xj,xt)∈V(L(D))such that N+(asi)=N-(ajt)={aij}in L(D).Therefore,L(D)is bi-super-connected.

On the other hand,let L(D)be bi-super-connected and there exists a minimum Vertex-cut U of L(D).Thus,there exist two Vertices asi=(xs,xi),ajt=(xj,xt)∈V(L(D))such that N+(asi)=U=N-(ajt).By the definition of line digraph,we known that there are|U|parallel arcs from xito xjin D.Since D is sim ple,we have|U|=1.Thusκ(L(D))=1.Therefore, λ(D)=1 by Lemma 2.Iffor any cut-arc(xi,xj)∈A(D),then there is no Vertex asisuch that N+(asi)={aij}or Vertex ajtsuch that N+(ajt)={aij},a contradiction.

Next,we characterize the bi-super-connected Cartesian product D1□D2of two digraphs D1and D2.In the following of this section,we w ill assume thatδ(D)=δ+(D)=δ-(D)for digraph D.For conVenience,we use the symbols ni,δi,κito denote the order,them inimum degree and the connectivity of digraph Di,for i=1,2.

By the definition of“bi-super-connected”,we known that if D1□D2is super-κ and there exists a minimum Vertex-cut U of D1□D2such that U=N+((x,y))=N-((x,y)),(x,y)∈V(D1□D2),then D1□D2is bi-super-connected.Thus,in the following theorem,we will consider that there exists a minimum Vertex-cut U of D1□D2such that U=N+((x,y))=N-((x,y)) does not hold for any Vertex(x,y)∈V(D1□D2).

The following theorem in［8］forκi=δi=1 is useful in our proof.

Theorem 4［8］Let D1and D2be two simple strongly connected digraphs and letƒor i=1,2.Iƒδi=κi,then D1□D2is super-κiƒand only iƒ,whereκ(D)=δ(D)=1,n≥2.

Therefore,ifκi=δi=1 for i=1,2,then D1□D2is super-κif and only if

Theorem 5 Let D1and D2be two strongly connected digraphs,then D1□D2is bi-superconnected iƒand only iƒtheƒollowing conditions hold:

i)κi=δi=1ƒor i=1,2,

iii)There exists a vertex x∈Viwith d+(x)=1 such that,and a vertex x∈Viwith d-(x)=1 such thatƒor i=1,2.

P roo f If i)and ii)hold,then D1□D2is super-κby Theorem 4 and there exists Vertex (x,y)∈V(D1□D2)such that U=N+((x,y))for each minimum Vertex-cut U.By i)and iii), U=N+((x,y))={(x,y1),(x1,y)}=N-((x1,y1))thus D1□D2is bi-super-connected.

On the other hand,if D1□D2is bi-super-connected,then D1□D2is super-κ.We first prove i).Without loss of generality,suppose thatδ1≥2.We assume that U is a minimum Vertex-cut of D1□D2.Since D1□D2is bi-super-connected,thus there are two Vertices(x,y)and(x′,y′)((x,y)/=(x′,y′))With N+((x,y))=U=N-((x′,y′)).Set,,then

Sinceδ1≥2 andδ2≥1,thus N+((x,y))/=N-((x′,y′)),a contradiction,i)holds.By Theorem 4,if i)holds and D1□D2is super-κ,then ii)holds.Finally,we prove iii).Without loss of generality,suppose that for any Vertex x∈V1With d+(x)=1 such thatwhereThere is a Vertex y∈V2With d+(y)=1,let,then U=N+((x,y))={(x′,y),(x,y′)}⊊N-((x′,y′))is a minimum Vertex-cut of D1□D2,and there is no(x′′,y′′)∈V(D1□D2)such that U=N-((x′′,y′′)),a contradiction.

Lemma 6［9］Let D=(V,A)be a strongly connected d-regular digraph.Iƒthere exists a vertex y∈V such thatƒor any vertex-cut,then D is a symmetric digraph.

Theorem 7 Let D1and D2be two strongly connected regular digraphs.Then D1□D2is bi-super-connected iƒ and only iƒ one oƒ the ƒollowing conditions holds:

i)D1and D2are symmetric digraphs and D1□D2is super-κ.

ii)D1and D2are directed cycles exceptƒor(k≥3),wheredenote the directed cycle oƒlength k.

P roo f If i)holds,D1□D2is super-κthen there is a Vertex(x.y)∈V(D1□D2)such that N+((x,y))=U for any minimum Vertex-cut.D1and D2are symmetric digraph, so N+((x,y))=U=N-((x,y)).Thus,D1□D2is bi-super-connected.If ii)holds,then D1□D2is bi-super-connected by Theorem 5.

On the other hand,if D1□D2is bi-super-connected,then D1□D2is super-κ,we consider two cases:

Case 1 If there exists a minimum Vertex-cut U of D1□D2such that U=N+((x,y))= N-((x,y)),(x,y)∈V(D1□D2),then there exists a Vertex x∈Visuch that U′=N+(x)= N-(x)for any Vertex-cut U′=N+(z)(or N-(z))of Difor i=1,2.By Lemma 6,D1and D2are symmetric digraphs,i)holds.

Case 2 If for any Vertex(x,y)∈V(D1□D2)such that U=N+((x,y))=N-((x,y)) for any minimum Vertex-cut U of D1□D2does not hold,thenδ1=δ2=1 by Theorem 5.Since D1and D2are strongly connected regular digraphs,we have,D1and D2are directed cycles, ii)holds.□

Finally,we characterize the bi-super-connected lexicographic product of two digraphs.

It is clear that if D1is an isolated Vertex,then D1［D2］D2,and if D2is an isolated Vertex,then D1［D2］D1.In the following,we always assume that D1and D2are strongly connected digraph With at least two Vertices.

Theorem 9［9］D1［D2］is super-κiƒand only iƒD1is a complete digraph and D2is super-κ.

Theorem 10 D1［D2］is bi-super-connected iƒand only iƒD1is a complete digraph and D2is bi-super-connected.

P roof If D1［D2］is bi-super-connected,then D1［D2］is super-κ,wehaVe D1isa com p lete digraph and D2is super-κby Theorem 9.ObVious D2is bi-super-connected.

On the other hand,if D2is bi-super-connected,then D2is super-κ.Since D1is a complete digraph,so we have D1［D2］is super-κby Theorem 9.The Vertex setis the out-neighbor and in-neighbor of,and D2is bi-super-connected,thus,D1［D2］is bi-super connected.

［1］MENG J X, ZHANG Z. Super-connected arc-transitive digraphs ［J］. Discrete Applied Mathematics, 2009, 157:653-658.

［2］CHIUE W S, SHIEH B S. On connectivity of the Cartesian product of two graphs ［J］. Applied Mathematics and Computation, 1999, 102: 129-137.

［3］XU J M, YANG C. Connectivity of Cartesian product graphs ［J］. Discrete Mathematics, 2006, 306: 159-165.

［4］MENG J X. Superconnectivity and super edge-connectivity of line graphs ［J］. Graph Theory Notes of New York,XL 2001: 12-14.

［5］XU J M, LV M, MA M J, HElLLWIG A. Super connectivity of line graphs ［J］. Information processing Letters,2005, 94: 191-195.

［6］ZHANG Z, LIU F X, MENG J X. Super-connected n-th interated line digraphs ［J］. OR Transanctions, 2005, 9:35-39.

［7］SHIEH B S. Super edge- and point-connectivities of the Cartesian product of regular graphs ［J］. Networks, 2002,40: 91-96.

［8］LIU J, MENG J X. Super-connected and super-arc-connected Cartesian product of digraphs ［J］. Information processing Letters, 2008, 108: 90-93.

［9］LIU J, MENG J X, ZHANG Z. Double-super-connected digraph ［J］. Discrete Applied Mathematics, 2010, 158:1012-1016.

［10］XU J M. Topological Structure and Analysis of Interconnection Networks ［M］. Dordrecht, Netherlands: Kluwer Academic publishers, 2001.

(责任编辑李艺)

有向图的双超连通性

李静静,刘娟
(新疆师范大学数学科学学院,乌鲁木齐830054)

简单有向图D(无环与重弧),如果满足每个最小点割都是某个点的出邻点集或入邻点集,则称D是超连通的.在超连通有向图D中,如果存在一个最小点割既是某个点的出邻点集又是某个点的入邻点集,则称D是双超连通的.主要研究了线图双超连通性的充要条件;同时,研究了笛卡尔积与字典积的双超连通性.

组合问题;超连通;双超连通性;线图;笛卡尔积

2015-01

国家自然科学基金(61363020,11301450);新疆维吾尔自治区青年科技创新人才培养工程(2013731011);新疆维吾尔自治区自然科学基金(2012211B21);新疆研究生科技创新项目(2014118)

李静静,女,硕士研究生,研究方向为图论与组合数学.E-mail:804474119@qq.com.

刘娟,女,教授,研究方向为图论与组合数学.E-mail:liu juan1999@126.com.

O 157 Document code:A

10.3969/j.issn.1000-5641.2016.01.011

1000-5641(2016)01-0091-05