Abstract The connectivity is an important measurement for the fault-tolerance of networks. To provide more accurate measures for the fault-tolerance of networks than the connectivity, some generalizations of connectivity have been introduced. Substructure connectivity and structure connectivity are two extended concepts of classical connectivity. As a variant of the popular network hypercube, the Möbius cubes is also a famous interconnection network in parallel and distributed systems. In this article, we calculate $H$-substructure connectivity and $H$-structure connectivity of Möbius cubes when $H$ is isomorphic to $P_{m},C_{m}$ and $K_{1,m}$.

Abstract A bipartite graph is Hamiltonian laceable if any two of its vertices in different partite sets are connected by a Hamiltonian path. A Hamiltonian laceable graph $G$ is called strongly Hamiltonian laceable if any two of its vertices in the same partite set are connected by a path of length $|V(G)|-2$. A Hamiltonian laceable graph $G$ (with two partite sets $V_0, V_1$) is called hyper-Hamiltonian laceable, if for any vertex $v \in V_{i}$ for $i \in \{0,1\}$, there is a Hamiltonian path of $G-\{v\}$ between any two vertices in $V_{1-i}$. In this paper, we focus on the edge-fault-tolerant strongly Hamiltonian laceability and hyper-Hamiltonian laceability on the class of Cayley graphs generated by transposition trees, which are a generalization of star graph and bubble-sort graph. For every $n$-dimensional Cayley graph generated by a transposition tree $\Gamma _n$, we show that $\Gamma _{n}-F$ is strongly Hamiltonian laceable for any $F \subseteq E(\Gamma _{n})$ with $|F|\leq n-3$, which generalizes results in [ 1, 11], and show that $\Gamma _{n}-F$ is hyper-Hamiltonian laceable for any $F \subseteq E(\Gamma _{n})$ with $|F|\leq n-4$.