| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 418804 | Discrete Applied Mathematics | 2009 | 7 Pages |
Let GG be a graph. The connectivity of GG, κ(G)κ(G), is the maximum integer kk such that there exists a kk-container between any two different vertices. A kk-container of GG between uu and vv, Ck(u,v)Ck(u,v), is a set of kk-internally-disjoint paths between uu and vv. A spanning container is a container that spans V(G)V(G). A graph GG is k∗k∗-connected if there exists a spanning kk-container between any two different vertices. The spanning connectivity of GG, κ∗(G)κ∗(G), is the maximum integer kk such that GG is w∗w∗-connected for 1≤w≤k1≤w≤k if GG is 1∗1∗-connected.Let xx be a vertex in GG and let U={y1,y2,…,yk}U={y1,y2,…,yk} be a subset of V(G)V(G) where xx is not in UU. A spanning k−(x,U)k−(x,U)-fan , Fk(x,U)Fk(x,U), is a set of internally-disjoint paths {P1,P2,…,Pk}{P1,P2,…,Pk} such that PiPi is a path connecting xx to yiyi for 1≤i≤k1≤i≤k and ∪i=1kV(Pi)=V(G). A graph GG is k∗k∗-fan-connected (or kf∗-connected ) if there exists a spanning Fk(x,U)Fk(x,U)-fan for every choice of xx and UU with |U|=k|U|=k and x∉Ux∉U. The spanning fan-connectivity of a graph GG, κf∗(G), is defined as the largest integer kk such that GG is wf∗-connected for 1≤w≤k1≤w≤k if GG is 1f∗-connected.In this paper, some relationship between κ(G)κ(G), κ∗(G)κ∗(G), and κf∗(G) are discussed. Moreover, some sufficient conditions for a graph to be kf∗-connected are presented. Furthermore, we introduce the concept of a spanning pipeline-connectivity and discuss some sufficient conditions for a graph to be k∗k∗-pipeline-connected.
