標題: 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-Apr-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
Appears in Collections:Articles


Files in This Item:

  1. 000264989500003.pdf