The Spanning Connectivity of the Burnt Pancake Graphs

Cherng CHIN  Tien-Hsiung WENG  Lih-Hsing HSU  Shang-Chia CHIOU  

IEICE TRANSACTIONS on Information and Systems   Vol.E92-D   No.3   pp.389-400
Publication Date: 2009/03/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E92.D.389
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Algorithm Theory
interconnection networks,  Hamiltonian cycles,  Hamiltonian connected,  container,  

Full Text: PDF>>
Buy this Article

Let u and v be any two distinct vertices of an undirected graph G, which is k-connected. For 1 w k, a w-container C(u, v) of a k-connected graph G is a set of w-disjoint paths joining u and v. A w-container C(u, v) of G is a w *-container if it contains all the vertices of G. A graph G is w *-connected if there exists a w *-container between any two distinct vertices. Let κ(G) be the connectivity of G. A graph G is super spanning connected if G is i *-connected for 1 i κ(G). In this paper, we prove that the n-dimensional burnt pancake graph Bn is super spanning connected if and only if n ≠ 2.