On the spanning connectivity and spanning laceability of hypercube-like networks

Abstract

Let $u$ and $v$ be any two distinct nodes of an undirected graph $G$, which is $k$-connected. For $1\le w\le k$, a $w$-container $C(u,v)$ of a $k$-connected graph $G$ is a set of $w$-disjoint paths joining $u$ and $v$. A $w$-container $C(u,v)$ of $G$ is a $w^{\ast }$-container if it contains all the nodes of $G$. A graph $G$ is $w^{\ast }$-connected if there exists a $w^{\ast }$-container between any two distinct nodes. A bipartite graph $G$ is $w^{\ast }$-laceable if there exists a $w^{\ast }$-container between any two nodes from different parts of $G$. Let $G_0=(V_0,E_0)$ and $G_1=(V_1,E_1)$ be two disjoint graphs with $\left|V_0\right|=\left|V_1\right|$. Let $E=\{(v,\varphi \left(v\right))\mid v\in V_0,\varphi \left(v\right)\in V_1$, and $\varphi :V_0\to V_1$ is a bijection$\}$. Let $G=G_0\oplus G_1=(V_0\cup V_1,E_0\cup E_1\cup E)$. The set of $n$-dimensional hypercube-like graph $H_n^{\prime }$ is defined recursively as (a) $H_1^{\prime }=\left\{K_2\right\}$, $K_2=$ complete graph with two nodes, and (b) if $G_0$ and $G_1$ are in $H_n^{\prime }$, then $G=G_0\oplus G_1$ is in $H_{n+1}^{\prime }$. Let $B_n^{\prime }=\{G\in H_n^{\prime }$ and $G$ is bipartite$\}$ and $N_n^{\prime }=H_n^{\prime }\setminus B_n^{\prime }$. In this paper, we show that every graph in $B_n^{\prime }$ is $w^{\ast }$-laceable for every $w$, $1\le w\le n$. It is shown that a constructed $N_n^{\prime }$-graph $H$ can not be $4^{\ast }$-connected. In addition, we show that every graph in $N_n^{\prime }$ is $w^{\ast }$-connected for every $w$, $1\le w\le 3$.