On the spanning fan-connectivity of graphs

Cheng-Kuan Lin, Jiann-Mean Tan, D. Frank Hsu, Lih-Hsing Hsu

Research output: Contribution to journalArticle

8 Scopus citations

Abstract

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.
Original languageEnglish
Pages (from-to)1342-1348
Number of pages17
JournalDiscrete Applied Mathematics
Volume157
Issue number7
DOIs
StatePublished - 6 Apr 2009

Keywords

  • Hamiltonian connected; Hamiltonian; Dirac Theorem; Menger Theorem; Ore Theorem; Connectivity; Spanning connectivity; Spanning fan-connectivity; Spanning pipeline-connectivity; Graph container

Fingerprint Dive into the research topics of 'On the spanning fan-connectivity of graphs'. Together they form a unique fingerprint.

  • Cite this

    Lin, C-K., Tan, J-M., Frank Hsu, D., & Hsu, L-H. (2009). On the spanning fan-connectivity of graphs. Discrete Applied Mathematics, 157(7), 1342-1348. https://doi.org/10.1016/j.dam.2008.11.014