On the Spanning Connectivity of Graphs—A Survey∗

Eminjan Sabir,SHANG Hui,MENG Jixiang

(College of Mathematics and System Sciences,Xinjiang University,Urumqi Xinjiang 830046,China)

Abstract: This is intended as a survey paper covering recent progresses in the filed of spanning connectivity,i.e.,the largest integer k such that a graph G contains i internally disjoint paths between any two distinct vertices of G for 1≤i≤k and the union of the i paths spans G.This paper also includes some results on related topics such as super spanning connectivity,spanning laceability,super spanning laceability of graphs and digraphs,as well as some research works in the future.

Key words:connectivity;hamiltonicity;spanning connectivity;interconnection networks

0 Introduction

For the graph definitions and notation we follow[1].LetG=(V,E)be an undirected connected graph.AHamilton cycle(path)of a graphGis a spanning cycle(spanning path)of it,i.e.,a cycle(path)that contains every vertex ofG.A graphGisHamiltonianif it has a Hamilton cycle,andGisHamilton-connectedif there exists a Hamilton path between any two distinct vertices ofG.

Theconnectivityκ(G)of a graphGis the minimum number of vertices whose removal leaves the remaining graph disconnected or trivial.It follows from famous Menger’s Theorem that there arekinternally-disjoint paths joining any two distinct vertices inGwhenkis no more than the connectivity κ(G)ofG[2].

Hamiltonicity and connectivity are two important issues in graph theory.Recently,as a hybrid concept and extension of these two concepts,the spanning connectivity of graphs has been defined and studied[3,4].Ak-container C(u,v)ofGbetween two distinct verticesuandvis a set ofkinternally-disjoint paths betweenuandv,andC(u,v)is called ak∗-containerofGbetweenuandvif it contains all vertices ofG.A graphGisk∗-connectedif there exists ak∗-container between any two distinct vertices.Thespanning connectivityof a graphG,denoted by κ∗(G),is defined as the largest integerksuch thatGisi∗-connected for 1 ≤i≤kifGis 1∗-connected and undefined otherwise.Thus,every 1∗-connected graph is Hamilton-connected,and every 2∗-connected graph is Hamiltonian.Hence indeedk∗-connectedness of graphs is a hybrid concept and natural extension of connectivity and hamiltonicity.A graphGissuper spanning connectedif κ∗(G)= κ(G).Clearly,the complete graphKnis super spanning connected ifn≥ 2.

It is known that the counterpart of Hamilton-connected graphs in bipartite graphs is known as Hamilton-lacebale graphs.A bipartite graph with bipartition(X,Y)isHamilton-laceableif there exists a Hamilton path joining any two vertices from different partite sets;that is,one inXand one inY.A bipartite graph isk∗-laceable if there exists ak∗-container between any two vertices from different partite sets.A 1∗-laceable graph is also known as Hamilton-laceable graph.Furthermore,a graphGis 2∗-laceable if and only if it is Hamiltonian.All 1∗-laceble graphs except thatK1andK2are 2∗-laceable.A bipartite graphGissuper spanning laceableifGisi∗-lacebale for alli,1 ≤i≤ κ(G).

There is a Menger type theorem similar to the spanning connectivity of a graph.Letxbe a vertex in a graphGand letU={y1,y2,···,yt}be a subset ofV(G)wherexis not inU.At−(x,U)-fan,Ft(x,U),is a set of internally-disjoint paths{P1,P2,···,Pt}such thatPiis a path connectingxandyifor 1 ≤i≤t.It is proved by Dirac[5]that a graphGisk-connected if and only if it has at leastk+1 vertices and there exists at−(x,U)-fan for every choice ofxandUwith|U|≤kandxU.Similarly,one can introduce the concept of a spanning fan[6].A spanningk−(x,U)-fan is ak−(x,U)-fan{P1,P2,···,Pk}such thatA graphGis-fan-connected(also written as-connected)if there exists a spanningk−(x,U)-fan for every choice ofxandUwith|U|≤kandxU.The spanning fan-connectivity of a graphG,(G),is defined as the largest integerksuch thatGis-connected for 1 ≤ ω ≤kifGis a-connected graph.

There is another Menger type theorem similar to spanning connectivity and spanning fan-connectivity of a graph.LetU={x1,x2,···,xt}andW={y1,y2,···,yt}be twot-subsets ofV(G).A(U,W)-pipeline is a set of internally-disjoint paths{P1,P2,···,Pt}such thatPiis a path connectingxiandyπ(i)where π is a permutation of{1,2,···,t}.It is known that a graphGisk-connected if and only if it has at leastk+1 vertices and and there exists a(U,W)-pipeline for every choice ofUandWwith|U|=|W|≤kandUW.Similarly,one can introduce the concept of spanning pipeline[6].A spanning(U,W)pipeline is a pipeline{P1,P2,···,Pk}such thatA graphGis-pipeline-connected(or-connected)if there exists a spanning(U,W)-pipeline for every choice ofUandWwith|U|=|W|≤kandUW.The spanning pipeline-connectivity of a graphG,(G),is defined as the largest integerksuch thatGisfor 1 ≤ ω ≤kifGis a-connected graph.

The rest of the paper is organized as follows.Section 1 generalizes some classic results.Section 2 investigates the spanning connectivity of some well known graphs.Section 3 discusses the spanning connectivity and spanning laceability of some interconnection networks.Section 4 provides directed version of spanning connectivity.Section 5 draws a conclusion.

1 Generalizing the Classics

Dirac[7]proved that any graphGwith at least three vertices and minimum degree δ(G)≥n(G)/2 is 2∗-connected,wheren(G)is the order ofG.Moreover,any graphGwith at least four vertices and δ(G)≥n(G)/2+1 is 1∗-connected.In[8]ak∗analogue of Dirac Theorem was obtained.

Theorem 1[8]IfGis a graph withn(G)/2≤δ(G)≤n(G)−2,then κ∗(G)≥2δ(G)−n(G)+2.

Corollary 1[8](G)≤ κ∗(G)≤ κ(G)≤ δ(G)ifGis a graph withn(G)/2+1 ≤ δ(G)≤n(G)−2.Moreover,Gis super spanning connected if κ(G)=(G).In particular,Gis super spanning connected if δ(G)=n−2.

In[8],they also studied the spanning connectivity of faulty graphs.Clearly,it suffices to consider uncomplete graphs.

Theorem 2[8]Assume thatGis a graph with at least six vertices and(n(G)/2)≤δ(G)≤n(G)−2.IfTis a vertex subset ofGwith|T|≤(G)−3,then κ∗(G−T)≥(G)−|T|.

The optimality of Theorem 2 is easily seen from the following example.

ExampleLetG=Kn,n,nbe a complete three partite graph with vertex setV1,V2,andV3where|V1|=|V2|=|V3|=n≥3.LetTbe a vertex subset ofV1with|T|=t≤n−1.Clearly,κ∗(G−T)=n−t+2=(G)−t.

Ore[9,10],and Bondy et al.[11]proved the following beautiful result.

Theorem 3[9−11]Assume that there exists two non-adjacent verticesuandvwithdG(u)+dG(v)≥n(G)thenGis 2∗-connected if and only ifG+uvis 2∗-connected.Moreover,dG(u)+dG(v)≥n(G)+1 thenGis 1∗-connected if and only ifG+uvis 1∗-connected.

This was extended as follows:

Theorem 4[12]Letkbe a positive integer.Assume that there exists two non-adjacent verticesuandvwithdG(u)+dG(v) ≥n(G)+kthenGis(k+2)∗-connected if and only ifG+uvis(k+2)∗-connected.Moreover,Gisi∗-connected if and only ifG+uvisi∗-connected for 1 ≤i≤k+2.

The following was also obtained in[9].

Theorem 5[9]Assume thatdG(u)+dG(v)≥n(G)+1 for non-adjacent verticesuandvofG.ThenGis 1∗-connected.

Lin[12]further showed:

Theorem 6[12]Letkbe an integer.Assume thatdG(u)+dG(v)≥n(G)+kfor non-adjacent verticesuandvofG.ThenGisi∗-connected for 1 ≤i≤k+2.

In[6]some relationship between κ(G),κ∗(G),and(G)were discussed.

Theorem 7[9](G)≤ κ∗(G)≤ κ(G)for anyconnected graph.Moreover,(G)= κ∗(G)= κ(G)=n(G)−1 if and only ifGis a complete graph.

Moreover,some sufficient conditions for a graph to be-connected were presented.

Theorem 8[9]Assume thatkis a positive integer.Letuandvbe two non-adjacent vertices ofGwithdG(u)+dG(v)≥n(G)+k.Then(G)≥k+1 if and only if(G+uv)≥k+1.

Similar to the spanning connectivity and spanning fan-connectivity,spanning pipeline connectivity was discussed in[6].

Theorem 9[9]Assume thatkis a positive integer.Letuandvbe two non-adjacent vertices ofGwithdG(u)+dG(v)≥n(G)+k.Then(G)≥kif and only if(G+uv)≥k.

For the hamiltonicity of graphs,another very interesting approach was introduced by Fan[13].He showed that we need not consider“all pairs of nonadjacent vertices”,but only a particular subset of these pairs.

Theorem 10[13]IfGis a 2-connected graph of ordernsuch that

thenGis Hamiltonian.

Theorem 10 was strengthened in[14],where the similar conditions were shown to imply the graph is Hamiltonconnected.

Theorem 11[14]IfGis a 3-connected graph of ordern≥4 such that

thenGis Hamilton-connected.

Naturally we have the following problem:

Problem 1Does there exist ak∗analogue of Fan’s Theorem?

2 Some well known graphs

2.1 Petersen graph and its generalizations

The Peteren graph is an important graph in graph theory and there are several generalizations of it.One of them is the class of generalized Petersen graphs introduced by Watkins[15],which has attracted much research throughout the years.Thegeneralized Petersen graph GP(n,k)has{0,1,2,...,n−1,0,1,2,...,(n−1)}as its vertex set.The edge set is,where the addition is performed modulon.Note thatGP(n,k)is bipartite if and only ifnis even andkis odd.It is clear thatGP(n,k)is 3-regular.Generalized Petersen graphGP(5,2)is illustrated in Fig 1.

For evennand oddk,since the vertex connectivity ofGP(n,k)is three andGP(n,k)is a bipartite graph,GP(n,k)is not 3∗-connected[3].Hence,they proved the following:

Theorem 12[3]GP(n,2)is 3∗-connected if and only ifn≡1,3(mod6).

Very recently,Wang et al.proved that:

Theorem 13[16]GP(n,3)is 3∗-connected if and only ifnis odd withn≥7.

For even integern,Kao et al.showed:

Theorem 14[17]GP(n,1)is 3∗-laceable if and only ifnis even withn≥4.

Another generalization of Petersen graph is double generalized Petersen graph proposed in[18].Given an integern≥3 andt∈Zn{0},2≤2t

O={{xi,xi+1},{yi,yi+1}|i∈Zn}(the outer edge),

I={{ui,vi+t},{vi,ui+t}|i∈Zn}(the inner edge),

S={{xi,ui},{yi,vi}|i∈Zn}(the spokes).

See Fig 2 an illustration of double generalized Petersen graphDP(5,2).

Recently,Wang proved the following nice result:

Theorem 15[19]AllDP(n,t)are 2∗-connected.

It is worthy of considering the following more general problem:

Problem 2Does everyDP(n,t)isk∗-connected or laceable fork=1,3?

Fig 1 The generalized Petersen graph GP(5,2)(the Petersen graph)

Fig 2 The double generalized Petersen graph DP(5,2)

2.2 Line Graphs

The line graph of a graphG,denoted byL(G),hasE(G)as its vertex set,and two vertices inL(G)are adjacent if and only if the corresponding edges inGare adjacent.

Zhan[20]proved thatL(G)is Hamilton connected if edge connectivity(G)≥ 4.Huang et al.generalized this result by proving the following:

Theorem 16[21]L(G)isk∗-connected ifGis a connected graph with(G)≥ 2k≥ 4.They also generalized the result above into spanning fan-connectivity.

Theorem 17[21]L(G)isk∗-fan-connected ifGis a connected graph with(G)≥ 2k≥ 4.

2.3 Power Graphs

LetG=(V,E)be a connected graph.Thes-th powerofG,denoted byGs,is the graph onV(G)such that two vertices are adjacent inGsif and only if their distance inGis at mosts.

Karaganis and Sekanina determined the following nice result independently.

Theorem 18[22,23]IfGis a connected graph of order at least 3,then its cubeG3is 1∗-connected.

This result is generalized as follows.

Theorem 19[24]IfGis a connected graph of order|V(G)|≥k+1≥4,thenGkisk∗-connected.

According to the work of[8],G2is 3∗-connected ifGis a hamiltonian graph of ordern≥ 4.A quite natural problem is:

Problem 3Find a minimum numberf=f(k,κ,d)such thatG fof a graphGwith connectivity κ≥ 1 and diameterdisk∗-connected.

3 Some interconnection networks

3.1 Hypercube-like graphs

Then-dimensional hypercube Qnhas the vertex-set consisting of 2nbinary strings of lengthn,two vertices being joined by an edge if and only if they differ in exactly one position.The hypercubeQnpossesses many attractive properties such as both connectivity and edge-connectivity aren,and it is bipartite[25].It is well known thatQnis Hamilton laceable[26].The result was extended as following.

Theorem 20[27]The hypercubeQnis super spanning laceable for any positive integern.

Motivated by the above theorem,Lin et al.studied the spanning connectivity of hypercube-like networks[28].

LetG0=(V0,E0)andG1=(V1,E1)be two disjoint graphs with the same number of nodes.A 1−1connectionbetweenG0andG1is defnied asE={(v,φ(v))|v∈V0,φ(v)∈V1,and φ :V0−→V1is a bijection}.We useG0⊕G1to denoteG=(V0∪V1,E0∪E1∪E).LetG=G0∪G1.

Then-dimensional hypercube-like graphsare defnied as follows:

The set ofbipartite n-dimensional-graph,,is defnied as follows:

(1)={K2},whereK2is the complete graph defnied on{a,b}with bipartitionV0={a}andV1={b}.

(2)Fori=0,1,letGibe a graph inwith bipartitionandLet φ be a bijection betweensuch that φ(v)∈ifv∈.ThenG=G0⊕G1is a graph in

Theorem 21[28]All bipartite hypercube-like graphs are super spanning laceable.

The fault-tolerance Hamiltonian laceability of the bipartite hypercube-like networks was studied by Lin et al.in[29].

Theorem 22[29]All bipartite hypercube-like graphs are(n−2)-edge fault Hamiltonian laceable.

Very recently,the result was generalized as follows.

Theorem 23[30]All bipartite hypercube-like graphs aref-edge faultk∗-laceable forf≤n−2 andf+k≤n.

For non-bipartite hypercube-like graphs,in[28]studied as following:

Theorem 24[28]All non-bipartite hypercube-like graphs arek∗-connected fork,1≤k≤3.

In the same paper,it was also shown that a constructed non-bipartite hypercube-like graph is not 4∗-connected.

Results about the special candidates of non-bipartite hypercube-like graphs are given below.

Then-dimensional augmented cube AQnhas 2nvertices,each labeled by ann-bit binary string.(1)AQ1=K2.(2)Forn≥ 2,AQnis obtained by taking two copies of augmented cubeAQn−1,denoted by,and adding 2×2n−1edges between the two as follows.LetV()={ix|x∈V(AQn−1)}(i=0,1).A vertexu=0un−2un−3...u0∈is adjacent to a vertexv=1vn−2vn−3...v0∈V()if and only if for every 0≤i≤n−2,one of the following two conditions holds:(a)ui=vi.In this case,the edge(u,v)is called a hypercubes edge;(b)ui=In this case,the edge(u,v)is called a complement edge[31].

Theorem 25[32]AQnis super spanning-connected if and only ifn3.

Two binary stringx=x2x1andy=x2y1arepair-related,denoted byx∼y,if and only if(x,y)∈{(00,00),(10,10),(01,11),(11,01)}.

Then-dimensional crossed cube,denoted byCQn,is such a graph,its vertex-set is the same asQn,two verticesx=xn···x2x1andy=yn···y2y1are linked by an edge if and only if there existsj,1≤j≤nsuch that

(a)xn···xj+1=yn···yj+1,

(b)xjyj,

(c)xj−1=yj−1if j is even,and

(d)x2ix2i−1∼ y2iy2i−1for each i=1,2,...,

Theorem 26[32]CQnis super spanning-connected ifn≥7.According to the results of Theorems 21,25 and 26,it is worth to consider the following problem:

Problem 4Determine the super spanning connectivity of non-bipartite hypercube like graphs.

3.2 Folded Hypercubes

As one of the most attractive variants of the hypercube,then-dimensional folded hypercube FQn,proposed by El-Amawy and Latifi[34],is a graph obtained from hypercubeQnby adding 2n−1edges,each of them is between nodesu=u1u2...unandwhereThe folded hypercubeFQnis an(n+1)-regular graph with connectivityn+1.The following was shown in[35].

Theorem 27[35]FQnis 1∗-laceable ifnis odd and 1∗-connected ifnis even.

This was generalized in[36].

Theorem 28[36]FQnis super spanning-laceable ifnis odd and super spanning-connected ifnis even.

3.3 Enhanced Hypercubes

Then-dimensional enhanced hypercube Qn,k(2≤k≤n)is obtained from the hypercubeQnby adding a complementary edge between two verticesu=un...u1andBy definition,if two verticesuandvinQn,k(2≤k≤n)are adjacent,thenH(u,v)=1 orH(u,v)=k.The enhanced hypercubeQn,k(2≤k≤n)is an(n+1)-regular graph with diameter[37].Whenk=n,Qn,nreduces to then-dimensional folded hypercubeFQn;hence the enhanced hypercube is a generalization of the folded hypercube.The following nice result was obtained in[38].

Theorem 29[38]Qn,kis super spanning-laceable ifkis odd and super spanning-connected ifmis even.

3.4 Tours Networks

Given integersk1,k2,...knwithki≥3,we defineZk1,k2,...kn={(x1,x2,...,xn)0≤xi≤ki−1,1≤i≤n}.Then-dimensional tours Tk1,k2,...knis a graph with vertex setV=Zk1,k2,...knand edge setE={uv|u=(u1,u2,...,un),v=(v1,v2,...,vn)∈Vand there is only anisuch thatui−vi= ±(mod ki),anduj=vjforji}.Then-dimensional toursTk1,k2,...knalso can be defined as Cartesian product of cycles,i.e.,Tk1,k2,...kn=Ck1×Ck2×···×Ckn.

For two dimensional tours networks,Ma et al.determined the following:

Theorem 30[36]Tk1,k2is super spanning-connected if at least one ofk1andk2is odd and super spanning laceable if bothk1andk2are even.

Theorem 30 inspires us to consider the following problem:

Problem 5What is the super spanning connectivity or super spanning laceability ofn-dimensional tours network?

3.5 Fully Connected Cubic Networks

Then-dimensional fully connected cubic networks FCCNnis defined recursively by taking the 3-dimensional cube as the basis graph.Forn≥1,theFCCNnis defined recursively as follows:

(1)FCCN1is the graph withV(FCCN1)=Z8andE(FCCN1)={(0,1),(0,2),(1,3),(2,3),(4,5),(4,6),(5,7),(6,7),(0,4),(1,5),(2,6),(3,7)}.Obviously,FCCN1is isomorphic toQ3.

(2)Whenn≥2,FCCNnis built from eight vertex-disjoint copies ofFCCNn−1by adding 28 edges.For 0≤k≤7,we letkFCCNn−1denoted a copy ofFCCNn−1with each vertex being prefixed withk,thenFCCNndefined by

V(FCCNn)=

E(FCCNn)=

The fully connected cubic networksFCCN1andFCCN2are illustrated in Fig 3.

The main result about the spanning connectivity of fully connected cubic networks is following:

Theorem 31[39]FCCNnis super spanning-connected forn≥2.

We will use the following notations in next sections.For convenience,we first supply some notations.We use Ωnto denote the group of all permutations onIn={1,···,n}.Letnandkbe two positive integers withk

3.6 Star Graphs and Pancake Graphs

Then-dimensional star graph S nhasn!nodes which labeled byn!permutations in Ωn.There is an edge between any two vertices if and only if their labels differ only in the first and another positions[40].Furthermore,S nis(n−1)-regular,(n−1)-connected.

Theorem 32[41]S nis super spanning-laceable if and only ifn3.

Theorem 33[42]LetF⊆E(S n)with|F|=f≤n−3 andn≥4.ThenS n−Fisi∗-laceable for everyi,1≤i≤n−1−f.

Moreover,fault tolerant spanning laceabilityofS nwas also determined in[42].

Theorem 34[42]

Fig 3 The fully connected cubic networks FCCN1 and FCCN2

Then-dimensional pancake graph PGnhasn!nodes which labeled byn!permutations in Ωn.There is an edge from a nodeito a nodejif and only ifjis a permutation ofisuch thati=i1i2···ikik+1···inandj=ik···i2i1ik+1···in,where 2≤k≤n[40].Moreover,PGnis(n−1)-regular,(n−1)-connected.

Theorem 35[41]PGnis super spanning-connected if and only ifn3.

Furthermore,they discuss the spanning connectivity of the faulty pancake graphs.LetFbe subset ofV(PGn)∪E(PGn).

Theorem 36[42]If|F|=f≤n−4 andn≥4.ThenPGn−Fisi∗-connected for every 1≤i≤n−1−f.

Moreover,they determined the following result.

Theorem 37[42]κ∗f(PGn)=n−4 ifn≥4.

Noting that both star graphs and pancake graphs are Cayley graphs.Some examples of hamiltonicity of Cayley graphs were founded in[43,44];it is interesting to consider the spanning connectivity or spanning laceability of Cayley graphs.

3.7 (n,k)-star Graphs

The(n,k)-star graph S n,khas node-setPn,k,and a nodep=p1p2···pi···pkis adjacent to a node:(a)pip2···pi−1p1pi+1···pk,wherei∈ {2,3,···,k}(swap-edge);(b)where(unswap-edge)[45].By defniition,S n,k(n>k≥2)is(n−1)-regular,(n−1)-connected.The(n,k)-star graphsS4,3 andS4,2 are illustrated in Fig 4.

Theorem 38[46]S n,kis super spanning-connected ifn≥3 and(n−k)≥2.

3.8 Arrangement Graphs

The(n,k)-Arrangement graph An,khas node-setPn,kand two nodes are adjacent if and only if they differ in exactly one position[47].Furthermore,An,kisk(n−k)-regular,k(n−k)–connected.

Theorem 39[48]An,kis(k(n−k))∗-connected if(n−k)≥2.

Fig 4 The(n,k)-star graphs S 4,3 and S 4,2

3.9 WK Recursive Networks

The WK-recursive networks is a class of recursively scalable networks that can be constructed hierarchically by grouping basic modules.A complete graph of any sizedcan be serve as the basic modules.We useK(d,t)to denote a WK-recursive network of levelt,each of whose basic modules is ad-vertex complete graph,whered≥1 andt≥1.Each vertex ofK(d,t)is labeled as at-digit radixdnumber.Vertexat−1at−2···a1a0is adjacent to(1)at−1at−2···a1b,whereba0and(2)whereaj−1jrepresentsj−1 consecutiveaj.An edge incident with verticesat−1at−2···a1bandat−1at−2···a1cwherebcis called a substituting edge.An edge incident with verticesat−1at−2···a1b(c)jandat−1at−2···a1c(b)jwherebcis called a flipping edge.An edge incident to(j)tfor 1≤j≤dis called an open edge,which is reserved for further expansion;hence,its other end vertex is unspecified[49].Moreover,κ(K(d,t))=d−1.TheWK-recursive graphsK5,1andK5,2are illustrated in Fig 5.

Fig 5 The WK-recursive graph K5,1 and K5,2

Theorem 40[50]K(d,t)is super spanning connected.

The results in this section imply that spanning connectivity or spanning laceability of almost all interconnection networks have been investigated.Fortunately,some new interconnection networks have been defined and studied recently such as balanced hypercube[51],twisted hypercube[52],connected cubic networks[53].

Problem 6Determine the spanning connectivity or laceablity of balanced hypercubes,twisted hypercubes,connected cubic networks.

4 Digraphs

According to the definition of the spanning connectivity of undirected graphs,Zhang et al.defined the directed version of the spanning connectivity[54].LetDbe digraph.A digraphDisstrongly connectedif there exists an(x,y)-path and a(y,x)-path for any two verticesxandyofD.We say thatDisk-strongly connectedif it remains strongly connected after the removal of any set of fewer thankvertices.A digraphDisweakly Hamiltonian connectedif there exists a Hamiltonian path between any two given vertices ofD.

Ak-containerofDbetween verticesuandv,C(u,v),is a set ofkinternally disjoint directed paths betweenuandv.Ak-containerC(u,v)ofDisstrong(resp.weak)-container(k≥ 2)if there is a set ofkinternally disjoint paths with the same direction(resp.with different directions allowed)betweenuandvand it contains all vertices ofD.A digraphDisk∗-strongly(resp.k∗-weakly)connectedif there exists a strong(resp.weak)k∗-container between any two distinct vertices fork≥ 2.Specially,we defineDis 1∗-connected ifDis weakly Hamiltonian connected(a 1∗-connected digraph is 1∗-strongly,and also 1∗-weakly connected).We define thestrong(resp.weak)spanning connectivityof a digraphD,(D)(resp.(D)),to be the largest integerksuch thatDis ω∗-strongly(resp. ω∗-weakly)connected for all 1≤ω≤k.

4.1 Tournaments

As application,the authors determined the spanning connectivity of famous tournaments.Atournament Tis a digraph such that each pair of vertices is joined by precisely one arc.Theirregularity i(T)of a tournamentTis the maximum|d+(x)−d−(x)|over all vertices ofxofT.They mainly determined the following:

Theorem 41[54]For allk≥0,a(2k+1)-strong tournament is(k+2)∗-weakly connected.

Theorem 42[54]For allk≥2,a(2k)-strong tournament isk∗-strongly connected.

Theorem 43[54]LetTbe a tournament withnvertices and irregularityi(T)≤k.Ifn≥6t+5k−3(t≥2),then(T)≥t+1.

Theorem 44[54]LetTbe a tournament withnvertices and irregularityi(T)≤k.Ifn≥6t+5k(t≥2),then(T)≥t.

This study is,actually,a natural extension of the work weak Hamiltonian connectedness of tournaments by Thomassen[55].

From the definition of the spanning connectivity of digraphs,it seems slightly difficult to investigate the spanning connectivity of general digraphs.However,it is maybe easier to determine the spanning connectivity of well known special digraphs such as De brujin and Kautz digraphs[56,57].

Problem 7Investigate the spanning connectivity of De brujin and Kautz digraph.

5 Remarks

In this paper,we survey many results on the spanning connectivity and spanning laceability of graphs and digraphs.More importantly,we list some typical problems in every section.In fact,these problems just examples of topics worth to study in the future.There are more problems such as the generalizations of sufficient conditions for graphs(digraphs)to be hamiltonian connected to spanning connectedness,what kind of conditions guarantee thatkconnected graphs to bek∗-connected etc.worth to further study.The new concept spanning edge connectivity is also a new direction to define and study due to its close relation to famous Menger’s Theorem and Euleraian graphs.

We close the paper with an interesting conjecture which was given by Li and Wu[58].

Conjecture(k+2)∗-connected graph is(k+1)∗-connected for any positive integerk.