The super spanning connectivity of arrangement graph

Pingshan Li, Min Xu

Published 2016-06-13Version 1

A $k$-container $C(u, v)$ of a graph $G$ 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 is a spanning subgraph of $G$. A graph $G$ is $k^*$-connected if there exists a $k^*$-container between any two different vertices of G. A $k$-regular graph $G$ is super spanning connected if $G$ is $i^*$-container for all $1\le i\le k$. In this paper, we prove that the arrangement graph $A_{n, k}$ is super spanning connected if $n\ge 4$ and $n-k\ge 2$.