View Related Documents

Abstract

A k -container C(u,v) of a graph G is a set of k disjoint paths between u and v. A k-container C(u,v) of G is a k * -container if it contains all vertices of G. A graph G is k * -connected if there exists a k *-container between any two distinct vertices of G. Therefore, a graph is 1*-connected (respectively, 2*-connected) if and only if it is Hamiltonian connected (respectively, Hamiltonian). A graph G is super spanning connected if there exists a k *-container between any two distinct vertices of G for every k with 1≤kκ(G) where κ(G) is the connectivity of G. A bipartite graph G is k * -laceable if there exists a k *-container between any two vertices from different partite set of G. A bipartite graph G is super spanning laceable if there exists a k *-container between any two vertices from different partite set of G for every k with 1≤kκ(G). In this paper, we prove that the enhanced hypercube Q n,m is super spanning laceable if m is an odd integer and super spanning connected if otherwise.

Keywords  Folded hypercubes - Enhanced hypercubes - Hamiltonian connected - Hamiltonian laceable - Super spanning connected - Super spanning laceable

Fulltext Preview

Image of the first page of the fulltext document