THE SPANNING CONNECTIVITY OF THE (n,k)-STAR GRAPHS
Authors:
- 1 April 2006
- journal article
- research article
- Published by World Scientific Pub Co Pte Ltd in International Journal of Foundations of Computer Science
- Vol. 17 (02) , 415-434
Abstract
A k-containerC(u, v) of a graph G is a set of k-disjoint paths joining u to v. A k-container C(u, v) is a k*-container if every vertex of G is incident with a path in C(u, v). A graph G is k*-connected if there exists a k*-container between any two distinct vertices u and v. A k-regular graph G is super spanning connected if G is i*-connected for all 1 ≤ i ≤ k. In this paper, we prove that the (n, k)-star graph Sn,k is super spanning connected if n ≥ 3 and (n-k) ≥ 2.Keywords
This publication has 4 references indexed in Scilit:
- The super connectivity of the pancake graphs and the super laceability of the star graphsTheoretical Computer Science, 2005
- Fault Hamiltonicity and fault Hamiltonian connectivity of the (n, k)‐star graphsNetworks, 2003
- TOPOLOGICAL PROPERTIES OF THE (n,k)-STAR GRAPHInternational Journal of Foundations of Computer Science, 1998
- A group-theoretic model for symmetric interconnection networksIEEE Transactions on Computers, 1989