pith. sign in

arxiv: 1803.08408 · v1 · pith:FGXHOLPRnew · submitted 2018-03-22 · 🧮 math.CO

Structure connectivity and substructure connectivity of twisted hypercubes

classification 🧮 math.CO
keywords connectivitykappamathcalrespconnectedhypercubesldotsstructure
0
0 comments X
read the original abstract

Let $G$ be a graph and $T$ a certain connected subgraph of $G$. The $T$-structure connectivity $\kappa(G; T)$ (or resp., $T$-substructure connectivity $\kappa^{s}(G; T)$) of $G$ is the minimum number of a set of subgraphs $\mathcal{F}=\{T_{1}, T_{2}, \ldots, T_{m}\}$ (or resp., $\mathcal{F}=\{T^{'}_{1}, T^{'}_{2}, \ldots, T^{'}_{m}\}$) such that $T_{i}$ is isomorphic to $T$ (or resp., $T^{'}_{i}$ is a connected subgraph of $T$) for every $1\leq i \leq m$, and $\mathcal{F}$'s removal will disconnect $G$. The twisted hypercube $H_{n}$ is a new variant of hypercubes with asymptotically optimal diameter introduced by X.D. Zhu. In this paper, we will determine both $\kappa(H_{n}; T)$ and $\kappa^{s}(H_{n}; T)$ for $T\in\{K_{1,r}, P_{k}\}$, respectively, where $3\leq r\leq 4$ and $1 \leq k \leq n$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.