Cubic $1$-Fault-Tolerant Hamiltonian Graphs, Globally $3^{\ast }$-Connected Graphs, and Super $3$-Spanning Connected Graphs

Abstract

A $k$-container $C(u,v)$ in a graph $G$ is a set of $k$ internally
vertex-disjoint paths between vertices $u$ and $v$. A $k^{\ast }$-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^{\ast }$-connected if there exists
a $k^{\ast }$-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^{\ast }$-connected for $1\le i\le k$. A graph $G$ is $1$-fault-tolerant
Hamiltonian if $G–F$ is Hamiltonian for any $F\subseteq V(G)$ and
$|F|=1$. In this paper, we prove that for cubic graphs, every
super $3$-spanning connected graph is globally $3^{\ast }$-connected and
every globally $3^{\ast }$-connected graph is $1$-fault-tolerant Hamiltonian.
We present examples of super $3$-spanning connected graphs, globally
$3^{\ast }$-connected graphs that are not super $3$-spanning connected,
$1$-fault-tolerant Hamiltonian graphs that are globally $1^{\ast }$-connected
but not globally $3^{\ast }$-connected, and $1$-fault-tolerant Hamiltonian
graphs that are neither globally $1^{\ast }$-connected nor globally $3^{\ast }$-connected.
Furthermore, we prove that there are infinitely many graphs in each
such family.