Cubic 1-fault-tolerant hamiltonian graphs, Globally 3*-connected graphs, and Super 3-spanning connected graphs

Abstract

A k-container C(u,v) in a graph G is a set of k internal vertex-disjoint paths between vertices u and v. A k*-container C(u,v) of G is a k-container such that C(u, v) contains all vertices of G. A graph is globally k*-connected if there exists a k*-container C(u, v) between any two distinct vertices u and v. A k-regular graph G is super k-spanning connected if G is i*-connected for 1 <= i <= k. A graph G is 1-fault-tolerant hamiltonian if G F is hamiltonian for any F subset of V boolean OR E and vertical bar F vertical bar = 1. In this paper, we prove that for cubic graphs, every super 3-spanning connected graph is globally 3*-connected and every globally 3*-connected graph is 1-faulttolerant hamiltonian. We present some examples of super 3-spanning connected graphs, some examples of globally 3*-connected graphs that are not super 3-spanning connected graphs, some examples of 1-fault-tolerant hamiltonian graphs that are globally 1*-connected but not globally 3*-connected, and some examples of 1-fault-tolerant hamiltonian that are neither globally 1*-connected nor globally 3*-connected. Furthermore, we prove that there are infinitely many graphs in each such family.