Super Spanning Connectivity of Augmented Cubes

Abstract

A \(k\)-container \(C(u, v)\) of \(G\) between \(u\) and \(v\) is a set of \(k\) internally disjoint paths between \(u\) and \(v\). A \(k\)-container \(C(u,v)\) of \(G\) is a \(k^*\)-container if it contains all nodes of \(G\). A graph \(G\) is \(k^*\)-connected if there exists a \(k^*\)-container between any two distinct nodes. The spanning connectivity of \(G\), \(\kappa^*(G)\), is defined to be the largest integer \(k\) such that \(G\) is \(\omega^*\)-connected for all \(1 \leq \omega \leq k\) if \(G\) is an \(1^*\)-connected graph and undefined if otherwise. A graph \(G\) is super spanning connected if \(\kappa^*(G) = \kappa(G)\). In this paper, we prove that the \(n\)-dimensional augmented cube \(AQ_n\) is super spanning connected.