標題: | On the spanning fan-connectivity of graphs |
作者: | Lin, Cheng-Kuan Tan, Jimmy J. M. Hsu, D. Frank Hsu, Lih-Hsing 資訊工程學系 Department of Computer Science |
關鍵字: | Hamiltonian connected;Hamiltonian;Dirac Theorem;Menger Theorem;Ore Theorem;Connectivity;Spanning connectivity;Spanning fan-connectivity;Spanning pipeline-connectivity;Graph container |
公開日期: | 6-四月-2009 |
摘要: | Let G be a graph. The connectivity of G, kappa(G), is the maximum integer k such that there exists a k-container between any two different vertices. A k-container of G between u and v, C(k)(u, v), is a set of k-internally-disjoint paths between u and v. A spanning container is a container that spans V(G). A graph G is k*-connected if there exists a spanning k-container between any two different vertices. The spanning connectivity of G, kappa*(G), is the maximum integer k such that G is w*-connected for 1 <= w <= k if G is 1*-connected. Let x be a vertex in G and let U = {y(1), y(2,) . . . , y(d)} be a subset of V(G) where x is not in U. A spanning k - (x, U)-fan, F(k)(x, U), is a set of internally-disjoint paths {P(1), P(2,) . . . , P(k)} such that P(i) is a path connecting x to y(i) for 1 <= i <= k and U(i=1)(k) V(P(i)) = V(G). A graph G is k*-fan-connected (or k(f)*-connected) if there exists a spanning Fk(x, U)-fan for every choice of x and U with vertical bar U vertical bar = k and x is not an element of U. The spanning fan-connectivity of a graph G, kappa(f)*(G), is defined as the largest integer k such that G is w(f)*-connected for 1 <= w <= k if G is 1(f)*-connected. In this paper, some relationship between kappa(G), kappa*(C), and kappa(f)*(G) are discussed. Moreover, some sufficient conditions for a graph to be k(f)*-connected are presented. Furthermore, we introduce the concept of a spanning pipeline-connectivity and discuss some sufficient conditions for a graph to be k*-pipeline-connected. Published by Elsevier B.V. |
URI: | http://dx.doi.org/10.1016/j.dam.2008.11.014 http://hdl.handle.net/11536/7378 |
ISSN: | 0166-218X |
DOI: | 10.1016/j.dam.2008.11.014 |
期刊: | DISCRETE APPLIED MATHEMATICS |
Volume: | 157 |
Issue: | 7 |
起始頁: | 1342 |
結束頁: | 1348 |
顯示於類別: | 期刊論文 |