Matching preclusion and conditional matching preclusion for hierarchical cubic networks

1.   Introduction

Let $G = (V, E)$ be a simple graph with vertex set $V(G)$ and edge set $E(G)$. A perfect matching in a graph is a set of edges such that each vertex is incident to exactly one of them, and an almost-perfect matching is a matching covering all but one vertex of $G$. A graph with an even number of vertices is an even graph, otherwise it is an odd graph. We use $G-F$ to denote the subgraph of $G$ obtained by deleting all the vertices and/or the edges of $F\subseteq V(G)\cup E(G)$.

The matching preclusion number of graph $G$, denoted by $mp(G)$, is the minimum number of edges whose deletion leaves the resulting graph without a perfect matching or an almost-perfect matching. Any such optimal set is called an optimal matching preclusion set. Birgham et al. ^[1] first introduced the definition of matching preclusion as a measure of robustness of interconnection networks in the event of edge failure. But beyond that, it also has connections to a few concepts related to theoretical topics, such as the conditional connectivity and extremal graph theory. For more on these topics see the surveys ^{[2,3,4,5,6,7,8,9]}.

Let $G$ be a graph with an even number of vertices. If it also has the property that the unique optimal matching preclusion sets are those whose elements are incident to a single vertex, then the following Proposition 1.1 holds:

Proposition 1.1. ^[4] Let $G$ be a graph with an even number of vertices. Then $mp(G)\leq{\delta(G)}$, where $\delta(G)$ is the minimum degree of $G$.

We call an optimal solution of the form given in Proposition 1.1 a trivial optimal matching preclusion set. If $mp(G) = \delta(G)$, then $G$ is maximally matched, and it is super matched if $mp(G) = \delta(G)$ and every optimal matching preclusion set is trivial. Obviously, the super matching network has better robustness.

The definition of conditional matching preclusion number was given in ^[4]. Let $G$ be a graph in which $mp(G) > 0$. The conditional matching preclusion number of a graph $G$, denoted by $mp_1(G)$, is the minimum number of edges whose deletion leaves the resulting graph with no isolated vertices and without a perfect matching or an almost-perfect matching. Any such optimal set is called an optimal conditional matching preclusion set. If a conditional matching preclusion set does not exist in $G$, that is, we cannot delete edges to satisfy both conditions, we leave $mp_1(G)$ undefined.

In ^[4], Cheng et al. investigated a basic obstruction to a perfect matching in the resulting graph with no isolated vertices. They found that for a basic obstacle set of perfect matching there would be exist a path $u-w-v$, where the degree of $u$ and the degree of $v$ are both one. They considered any such path $u-w-v$ in the original graph and defined that $\nu_e(G) = min\{d_G(u)+d_G(v)-2-y_G(u, v)\colon$there exists a 2-path between $u$ and $v$$\}$, where $d_G(.)$ is the degree function, and $y_G(u, v) = 1$ if $u$ and $v$ are adjacent and $0$ otherwise. Similar to Proposition 1.1, they obtained the following Proposition 1.2:

Proposition 1.2. ^[4] Let $G$ be a graph with an even number of vertices. Suppose that every vertex in $G$ has degree at least $3$. Then $mp_1(G)\leq{\nu_e(G)}$.

We call an optimal solution of the form induced by a $2$-path with value $\nu_e(G)$ a trivial optimal conditional matching preclusion set. If $G$ is a super matched graph and $mp_1(G) = \nu_e(G)$, then it is conditionally maximally matched. If, in additional, all optimal solutions are trivial, then it is conditionally super matched.

At present, matching preclusion set(or conditional matching preclusion set) for various basic interconnection networks has attracted much attention and research interest. For instance, the matching preclusion number for balanced hypercubes was investigated in ^[10]. In ^[11], Cheng et al. considered conditional matching preclusion for the arrangement graphs. Wang et al. ^[12] showed that the conditional matching preclusion number for $k$-ary $n$-cube is $4n-2$. For more details one can refer to ^{[2,3,4,5,6,10,11,12,13]} and reference therein.

The hierarchical cubic network $HCN_n$ was introduced by Ghose in ^[14]. For papers on hierarchical cubic network, we refer to the readers to ^[15] for a sample of results and additional references for $HCN_n$. The $HCN_n$ has many desirable properties such as topological structure. The hierarchical cubic network $HCN_n(n\geq2)$ can be decomposed into $2^n$ clusters, where each cluster is isomorphic to an $n$-dimensional hypercube $Q_n$. The matching preclusion and conditional matching preclusion of hypercube have been studied by ^[1] and ^[4] respectively. In this paper, we investigate the matching preclusion number and conditional matching preclusion number for hierarchical cubic networks. In Section $2$, we introduce some notations, definitions and properties used throughout the paper. In Section $3$, we discuss the matching preclusion number of $HCN_n$ and characterize all the optimal matching preclusion sets of $HCN_n$. Finally, we consider the conditional matching preclusion number of $HCN_n$ and all the optimal conditional matching preclusion sets of $HCN_n$ are categorized in Section $4$.

2.   Preliminaries

For a path, the length of it is the number of edges contained in it. Denote the path of length of $k(k\geq 1)$ by $k$-path. For any vertex $u\in V(G)$, use $N_G(u)$ to denote the neighborhood of $u$, that is, the set of vertices adjacent to $v$. The distance $d_G(u, v)$, between a pair of vertices $u$ and $v$ in $G$, is the length of a shortest path joining $u$ and $v$.

The Hamming distance, denoted by $d_{H}(u, v)$, between any two vertices $u$ and $v$, is the number of different positions between the binary strings of $u$ and $v$.

Let $V_n$ be the set of binary sequence of length $n$, i.e., $V_n = \{x_1x_2\cdots{x_n}\colon{x_i}\in\{0, 1\}, 1\leq{i}\leq{n}\}$. For $x = x_1x_2\cdots{x_n}\in{V_n}$, the element $\overline{x} = \overline{x}_1 \overline{x}_2\cdots\overline{x}_n\in V_n$ is called the bitwise complement of $x$, where $\overline{x}_i = \{0, 1\}\backslash\{x_i\}$ for each $i\in\{1, 2, \cdots, n\}$.

The $n$-dimensional hypercube network $Q_n$ is an cube, shortly $n$-cube, with its vertex-set $V_n$, and two vertices are adjacent if and only if they differ exactly in one coordinate. Fig. 1 shows a $Q_3$. For the sake of simplicity, we use $xQ_n$ to denote the Cartesian product $\{x\}\times Q_n$ of a vertex $x$ and a hypercube network $Q_n$.

Definition 2.1. ^[14] An $n$-dimensional hierarchical cubic network $HCN_n$ with vertex-set $V_n\times{V_n}$ is obtained from $2^n$ $n$-cubes $\{xQ_n\colon{x}\in{V_n}\}$ by adding edges between two $n$-cubes, called crossing edges, according to the following rule. A vertex $(x, y)$ in $xQ_n$ is linked to

(1) $(y, x)$ in $yQ_n$ if $x\neq{y}$ or

(2) $(\overline{x}, \overline{y})$ in $\overline{x}Q_n$ if $x = y$.

The vertex $(y, x)$ in $yQ_n$ or $(\overline{x}, \overline{y})$ in $\overline{x}Q_n$ is called on external neighbor of $(x, y)$ in $xQ_n$.

The edges between any two different $Q_n$ of $HCN_2$ are denoted by the crossing edges. And a $2$-dimensional hierarchical cubic network $HCN_2$ is shown in Fig. 2.

From Definition 2.1, it is easy to obtain the following property about crossing edges in $HCN_n$.

(1) There are two crossing edges between two $n$-cubes $xQ_n$ and $yQ_n$ if and only if $x$ and $y$ are complementary, otherwise there is only.

(2) The set of crossing edges consists of a perfect matching of $HCN_n$.

For $Q_n$, the results on the matching preclusion and the conditional matching preclusion of it are as follows.

Lemma 2.2. ^[1] Let $n\geq2$. Then $mp(Q_n) = n$ and $Q_n$ is super matched.

Lemma 2.3. ^[1] Let $n\geq3$. Then $mp_1(Q_n) = 2n-2$ and $Q_n$ is conditionally super matched.

Let $V_n = \{x^1, x^2, \cdots, x^{2^n}\}$, $x^1Q_n, x^2Q_n, \cdots, x^{2^n}Q_n$ be $2^n$ $n$-cubes in $HCN_n$. For $(z, z')\in E(HCN_n)$, and $z\in V(x^iQ_n)$, $z'\in V(x^jQ_n)$ where $1\leq i\neq j\leq 2^n$, then $z'$ is called the external neighbor of $z$. For notational simplicity, suppose that $x = x^1$. For a graph $G$, $v, w\in V(G)$, if there are $t(t\geq 2)$ paths joining $v$ and $w$, say $P_1, \ldots, P_t$ such that $V(P_i)\cap V(P_j) = \{v, w\}$ for $1\leq i, j\leq t, i\neq j$, then these paths are denoted by internally vertex-disjoint paths.

Lemma 2.4. Let $u$ be a vertex of $HCN_n$, and $u'$ be its external neighbor. Then there exist $n$ internally vertex-disjoint $7$-paths joining endpoints $u$ and $u'$.

Proof. Without loss of generality, suppose $u\in V(xQ_n), u = (x, y)$. Let $x_i, y_i, \overline{x}_i(1\leq i\leq n)$ be the binary sequence of length $n$ which differ from $x, y, \overline{x}$ in the $i$th bit only respectively, and $N_{xQ_n}(u) = \{u_i = (x, y_i), 1\leq i\leq n\}$.

Suppose $d = d_H(x, y)$, then $0\leq d\leq{n}$. We consider the following two cases.

Case 1. $d = 0$, that is $x = y$, $u = (x, x)$, $u' = (\overline{x}, \overline{x})$.

So $d(x, x_i) = 1$, the external neighbor of $u_i = (x, x_i)(1\leq i\leq n)$ is $(x_i, x)$ in $x_iQ_n$ respectively. For each vertex $(x_i, x)(1\leq i\leq n)$, $N_{x_iQ_n}((x_i, x)) = \{(x_i, x_1), (x_i, x_2), \ldots, (x_i, x_n)\}$. For $(\overline{x}, \overline{x})\in{V(\overline{x}Q_n)}$, $N_{\overline{x}Q_n}((\overline{x}, \overline{x})) = \{(\overline{x}, \overline{x}_1), (\overline{x}, \overline{{x}}_2), \ldots, (\overline{x}, \overline{{x}}_n)\}$. For each vertex $(\overline{x}, \overline{x}_i)(1\leq i\leq n)$, its external neighbors is $(\overline{{x}}_i, \overline{x})$ in $\overline{{x}}_iQ_n$, $N_{\overline{{x}}_iQ_n}((\overline{{x}}_i, \overline{x})) = \{(\overline{{x}}_i, \overline{{x}}_1), (\overline{{x}}_i, \overline{{x}}_2), \cdots, (\overline{{x}}_i, \overline{{x}}_n)\}$. The paths $\{(x, x)-(x, x_i)-(x_i, x)-(x_i, x_i)-(\overline{{x}}_i, \overline{{x}}_i)-(\overline{{x}}_i, \overline{x})-(\overline{x}, \overline{{x}}_i)-(\overline{x}, \overline{x}), 1\leq i\leq n\}$ are the desired paths.

Case 2. $d\geq1$, then $u' = (y, x)$.

Then $N_{xQ_n}(u) = \{(x, y_i), i = 1, 2, \cdots, n\}$, and $N_{yQ_n}(u') = \{(y, x_i), i = 1, 2, \cdots, n\}$.

If $d\geq2$, the external neighbors of $(x, y_i)$ and $(y, x_i)$ are $(y_i, x)$ and $(x_i, y)$ respectively where $1\leq i\leq n$. And $N_{y_iQ_n}((y_i, x)) = \{(y_i, x_1), (y_i, x_2), \cdots, (y_i, x_n)\}$, $N_{x_iQ_n}((x_i, y)) = \{(x_i, y_1), (x_i, y_2), \cdots, (x_i, y_n)\}$. The paths $\{(x, y)-(x, y_i)-(y_i, x)-(y_i, x_i)-(x_i, y_i)-(x_i, y)-(y, x_i)-(y, x), 1\leq i\leq n\}$ are the desired paths.

If $d = 1$, there is some $i$ such that $x = y_i$ and $y = x_i$. The $i$th path joining endpoints $u$ and $u'$ is $(x, y)-(x, x)-(\overline{x}, \overline{x})-(\overline{x}, \overline{y})- (\overline{y}, \overline{x})-(\overline{y}, \overline{y})-(y, y)-(y, x)$. And we can find the remaining $n-1$ paths by the case $d\geq 2$, completing the proof.

Let $Z\subseteq V(G)$ and $Y\subseteq V(G)\setminus Z$, the $(Y, Z)$-paths is a family of internally vertex-disjoint paths starting at a vertex $y\in Y$ ending at a vertex $z\in Z$ and whose internally vertices belong neither to $Y$ nor $Z$. By Lemma 2.4, we can obtain the following corollary easily.

Corollary 2.5. Let $u$ be a vertex of $HCN_n$, and $u'$ is its external neighbor, $U = N_{HCN_n}(u)-u'$. Then there are $n$ internally vertex-disjoint paths joining $u'$ and $U$.

3.   The matching preclusion number of $HCN_n$

Let $C$ denote the set of all crossing edges of $HCN_n$. Then $E(HCN_n) = \cup^{2^n}_{i = 1}E(x^iQ_n)\cup C$. Suppose $F\subseteq E(HCN_n)$ be a fault edge set of $HCN_n$, $F_i = F\cap{E(x^iQ_n)}(i = 1, 2, \cdots, 2^n)$, $F_c = F\cap C$, then $F = \cup^{2^n}_{i = 1}F_i\cup F_c$.

Theorem 3.1. Let $n\geq2$. Then $mp(HCN_n) = n+1$.

Proof. As $\delta(HCN_n) = n+1$, $mp(HCN_n)\leq{n+1}$. And $HCN_n$ is made up of $2^n$ $n$-cubes and a perfect matching, by Lemma 2.2, $mp(Q_n) = n$. Then $mp(HCN_n)\geq{n+1}$. Thus $mp(HCN_n) = {n+1}$.

Theorem 3.2. Let $n\geq2$. Then $mp(HCN_n) = n+1$. Moreover, $HCN_n$ is super matched.

Proof. By Theorem 3.1, $mp(HCN_n) = n+1$, we now classify the optimal solutions. Let $F$ be any optimal matching preclusion set of $HCN_n$, $|F| = n+1$, we need to prove $HCN_n-F$ has no perfect matchings. As $C$ is a perfect matching of $HCN_n$, $|F_c|\geq 1$ and $x^iQ_n-F_i$ has no perfect matching for some $i(i = 1, 2\ldots, n)$. For notational convenience, we may assume that $xQ_n-F_1(x = x^1)$.

$xQ_n$ is isomorphic to $Q_n$, by Lemma 2.2, $|F_1|\geq{n}$. And $|\cup^{2^n}_{i = 1}F_i|\leq{n}$, thus $|F_1| = n$, $|F_i| = 0(i = 2, \cdots, 2^n)$ and $xQ_n-F_1$ has an isolated vertex, say $u = (x, y)$. If the crossing edge $(u, u')\in F$, then $u$ is an isolated vertex in $HCN_n-F$, thus $(u, u')\notin F$. If $d_H(x, y)\geq 2$. By Lemma 2.4, choose one path joining $u$ and $u'$, say $P: u = (x, y)-(x, y_i)-(y_i, x)-(y_i, x_i)-(x_i, y_i)-(x_i, y)-(y, x_i)-(y, x) = u'$ for some $i\in \{1, 2, \ldots, n\}$. And $Q_n$ is made up of $n$ edge-disjoint perfect matchings, so $xQ_n-\{(x, y), (x, y_i)\}$, $y_iQ_n-\{(y_i, x), (y_i, x_i)\}$, $x_iQ_n-\{(x_i, y_i), (x, y)\}$, $yQ_n-\{(y, x_i), (y, x)\}$ have perfect matchings, say $M_{x}$, $M_{y_i}$, $M_{x_i}$, $M_y$. And $x^iQ_n-F_i$ has a perfect matching for $x^i\in V_n\backslash\{x, y_i, x_i, y\}$, say $M_{x^i}$. Thus $M = M_{x}\cup M_{y_i}\cup M_{x_i}\cup M_y\bigcup_{x^i\in V_n\backslash\{x, y_i, x_i, y\}}M_{x^i}\cup((x, y_i), (y_i, x))\cup((y_i, x_i), (x_i, y_i))\cup((x_i, y), (y, x_i))\cup(u, u')$ be a perfect matching of $HCN_n-F$. If $d_H(x, y)\neq 2$, the perfect matching of $HCN_n-F$ can be obtained similarly, completing the proof.

4.   The conditional matching preclusion of $HCN_n$

Theorem 4.1. Let $n\geq3$. Then $mp_1(HCN_n) = 2n$.

Proof. Since $\nu_e(HCN_n) = 2n$, $mp_1(HCN_n)\leq 2n$. Let $F$ be any conditional matching preclusion set of $HCN_n$ and $|F|\leq 2n-1$, it is enough to show that $HCN_n-F$ has a perfect matching if $HCN_n-F$ has no isolated vertices. By the structure of $HCN_n$, we know that $|F_c|\geq 1$. We can claim that there is only one of $\{x^iQ_n-F_i, 1\leq i\leq 2^n\}$ with no prefect matching. Otherwise, without loss of generality, suppose both $xQ_n-F_1$ and $x^2Q_n-F_2$ have no prefect matching, then $|F_1|\geq n$ and $|F_2|\geq n$ by Lemma 2.2. And $|F|\geq |F_1|+|F_2|+|F_c|\geq 2n+1$, a contradiction with $|F|\leq 2n-1$. For notational convenience, we may assume that $xQ_n-F_1$. Thus $|F_1|\geq n$. And as $|F| = |F_1|+\cdots+|F_{2^n}|+|F_c| = 2n-1$, then $|F_i|\leq n-2$ for $i\in \{2, 3, \ldots, 2^n\}$. We consider the following two cases.

Case 1. $|F_c|\geq 2$.

Then $|F_1|+\cdots+|F_{2^n}|\leq 2n-3$, $|F_1|\leq 2n-3$. Let $|F_c| = i(i\geq 2)$, $|F_1|\leq 2n-(i+1)$, and $|F_c|\leq n-1$ for $|F_1|\geq n$. From Lemma 2.3, $xQ_n-F_1$ has an isolated vertex, otherwise $xQ_n-F_1$ has a perfect matching. For $xQ_n$ consists of $n$ edge-disjoint perfect matchings, then $xQ_n-u$ has $n$ edge-disjoint almost perfect matchings. And $|F_1\cap E(xQ_n-u)|\leq n-(i+1)$, there exists at least $(i+1)$ edge-disjoint almost perfect matchings of $xQ_n-(F_1\cup \{u\})$. Without loss of generality, suppose the $i+1$ unmatched vertices are $u_1, u_2, \cdots, u_{i+1}$. As there is no isolated vertex in $HCN_n-F$, $(u, u')\notin F$. By Corollary 2.5, there exist $(i+1)$ internally vertex-disjoint paths joining $u'$ and $\{u_1, \ldots, u_{i+1}\}$, say $P'_1, \ldots, P'_{i+1}$. And $|F_c| = i$, thus there is at least one path of $\{P'_1, \ldots, P'_{i+1}\}$ and none of its crossing edges is in $F_c$, say $i = 1$. Thus $P_1$ is a $7$-path joining endpoints $u$ and $u'$, we can obtain the perfect matching of $HCN_n-F$ by the proof of Theorem 3.2.

Case 2. $|F_c| = 1$.

Then $|F_1|+\cdots+|F_{2^n}| = 2n-2$. If $xQ_n-F_1$ has an isolated vertex. Similar to the proof above, we can obtain the perfect matching of $HCN_n-F$ easily.

Now suppose $xQ_n-F_1$ has no isolated vertex. As $xQ_n-F_1$ has no perfect matching, then $F_1$ is a trivial conditional matching preclusion set of $HCN_n$, namely $|F_1| = 2n-2$, $|F_i| = 0$ for $2\leq i\leq 2^n$. For notational simplicity, we may assume that it is induced by $u_1-u-u_2$. Let $(x, y^j_i)(j = 2, \cdots, n)$ be adjacent to $(x, y_i)(i = 1, 2)$ such that $y_i^j$ differs from $y_i$ in the $j$th bit only, and $u'_1, u'_2$ be the external neighbors of $u_1$ and $u_2$. By $|F_c| = 1$, either $(u_1, u'_1)\notin F_c$ or $(u_2, u'_2)\notin F_c$, say $(u_1, u'_1)$. Let $N_{xQ_n}(u_1) = \{u, v_1, \ldots, v_{n-1}\}$. By Corollary 2.5, there are $n-1$ internally vertex-disjoint $7$-paths joining $u_1'$ and $\{v_1, \ldots, v_{n-1}\}$, say $R_i$ for $1\leq i\leq n-1$. As $n\geq 3$ and $|F_c| = 1$, there is at least one path of $\{R_1, \ldots, R_{n-1}\}$ such that none of its crossing edges is in $F_c$, say $R_1$. The perfect matching induced by $R_1$ is denoted as $M_1$. And $xQ_n-(F_1\cup (u_1, v_1))$ has a perfect matching, say $M_{x^1}$. $\cup_{i = 1}^{2^n}x^iQ_n-(R_1-\{u_1, v_1\})$ also has a perfect matching, say $M'$, then $M = M_{x^1}\cup M_1\cup M'$ is a perfect matching of $HCN_n-F$.

Lemma 4.2. ^[1] Let $n\geq 3$. Let $F$ be a conditional matching preclusion set in $Q_n$ with $|F| = 2n-1$. Then there exists $f, f'\in F$ such that $f$ and $f'$ are independent and both $Q_n-(F-\{f\})$ and $Q_n-(F-\{f'\})$ contain a perfect matching.

From the structure of $Q_n$, we know that there is a fact: for $n\geq 3$, suppose $P$ be a $3$-path of $Q_n$, then $Q_n-P$ has a perfect matching. Thus we can obtain the following lemmas.

Lemma 4.3. Let $v, w\in{V(Q_n)}$ and $d(v, w) = 3$. Then $Q_n-\{v, w\}$ has a perfect matching.

Lemma 4.4. Let $F'$ be a fault edge set of $Q_3$ with $|F'|\leq 4$, $v, w\in V(Q_3)$, $d(v, w) = 3$. If $v$ is an isolated vertex of $Q_3-F'$, then $Q_3-F'$ has an almost perfect matching such that $w$ is unmatched.

Proof. Without loss of generality, let $v = 000$, then $w = 111$. As $d(v) = 3$, $|E(Q_3-v)\cap{F'}| = 1$. For any edge of $E(Q_3-v)$, we can find an almost perfect matching and $w$ is unmatched.

Lemma 4.5. For $n\geq 3$, let $F'$ be a fault edge set of $Q_n$ with $|F'|\leq 2n-2$, $v, w_1, \ldots, w_{n-1}\in{V(Q_n)}$, $d(v, w_i) = 3(i = 1, \ldots, n-2)$. If $v$ is an isolated vertex of $Q_n-F'$, then $Q_n-F'$ has an almost perfect matching and $w_i(i = 1, \ldots, n-2)$ is unmatched.

Proof. We complete the lemma by induction on $n$. For $n = 3$, the conclusion holds by Lemma 4.4, now suppose $n\geq 4$ and the Lemma is true for $n-1$.

$Q_n$ contains two $(n-1)$-dimensional $Q_{n-1}$, say $Q^0_{n-1}$ and $Q^1_{n-1}$, with the first bit is $0$ and $1$ respectively, the perfect matching between $Q^0_{n-1}$ and $Q^1_{n-1}$ is defined by $M$. Let $F'_i = F'\cap{Q^i_{n-1}}(i = 0, 1)$ and $F_M = F'\cap M$. Hence $F' = F'_0\cup F'_1\cup F_M$. Without loss of generality, we can assume that $v\in V(Q^0_{n-1})$. As $v$ is an isolated vertex of $Q_n-F$, $|F_M|\geq 1$. If $|F_M|\geq 2$, hence $|F'_0|+|F'_1|\leq 2n-4$ and $|F'_i|\leq 2n-4$ for $i = 0, 1$. By inductive assumption, the conclusion holds. Now suppose $|F_M| = 1$, $|F'_0| = 2n-3$ and $|F'_1| = 0$.

Denote the neighbors of $v$ in $Q^0_{n-1}$ by $v_i(1\leq i\leq n-1)$. Let the external neighbors of $v$ and $v_i(1\leq i\leq n-1)$ be $v'$ and $v'_i$. For $Q^0_{n-1}$ consists of $(n-1)$-edge disjoint perfect matchings, $Q^0_{n-1}-v$ must contain $(n-1)$-edge disjoint almost perfect matchings, and $|E(Q^0_{n-1}-v)\cap F|\leq n-2$, there exists an almost perfect matching such that $v_i$ is unmatched for some $i$, say $v_1$. And $Q^0_{n-1}-\{v, v_1\}$ has a perfect matching, say $M_0$. As $|F_M| = 1$, then $(v_1, v'_1)\notin F_M$. Let $N_{Q^1_{n-1}}(v'_1) = \{v', w_2, \ldots, w_{n-1}\}$ and $w_1 = v'$. As $|F_1| = 0$, $Q^1_{n-1}-\{v'_1\}$ have $(n-1)$-edge disjoint almost perfect matching such that $w_i$ is unmatched, and $d(v, w_i) = 3$, completing the proof.

Lemma 4.6. For $n\geq 3$ and any two vertices of $V(x^iQ_n)(1\leq i\leq 2^n)$ such that the distance between them is $3$. Then there is a cycle $L$ of even order and $V(L)$ contains the two vertices.

Proof. For notational convenience, let $i = 1$, $u = (x, y)$, $v = (x, y')$. As $d(u, v) = 3$, then $d_{H}(y, y') = 3$. We complete the proof according to the value of $d_H(x, y)$.

Case 1. $d_H(x, y) = 0\ \rm{or}\ 3$.

Then $d_{H}(x, y') = 3\ \rm{or}\ 0$, we only need to consider that $d_H(x, y) = 0$.

For $n = 3$, we can assume that $u = (000,000)$, $v = (000,111)$. Hence $L:(000,000)-(111,111)-(111,110)-(111, ,100)-(111,000)$$-(000,111)-(000,011)-(000,001)-(000,000)$.

For $n\geq 4$, without loss of generality, suppose that $u = (0^n, 0^n), v = (0^n, 0^{n-3}111)$. Then $L:(0^n, 0^n)-(1^n, 1^n)-(1^n, 1^{n-3}110)-(1^n, 1^{n-3}100)-(1^n, 1^{n-3}000)-(1^{n-3}000, 1^n)$$-(1^{n-3}000, 1^{n-3}110) -(1^{n-3}000, 1^{n-3}100)-(1^{n-3}000, 1^{n-3}000)$$-(0^{n-3}111, 0^{n-3}111)-(0^{n-3}111, 0^{n-3}110) -(0^{n-3}111, 0^{n-3}100)$$-(0^{n-3}111, 0^{n-3}000)-(0^{n}, 0^{n-3}111)-(0^{n}, 0^{n-3}110)-(0^{n}, 0^{n-3}100)-(0^{n}, 0^{n})$.

Case 2. $d_H(x, y)\neq 0, 3$.

Let $P: u = (x, y)-(x, z)-(x, w)-(x, y')$ denote a $3$-path of $xQ_n$. Then we can obtain the cycle $L:(x, y)-(x, z)-(x, w)-(x, y')-(y', x)-(y', x')-(x', y')$$-(x', w)-(x', z)-(x', y)-(y, x') -(y, x)-(x, y)$ with $d_H(x, x') = 1$ and $x'\neq y$, completing the proof.

By the above lemma, we obtain that there is a path of length odd joining endpoints $u$ and $v$. The following Lemmas show that there are $2$ internally vertex-disjoint paths between the external neighbors of two vertices of $HCN_n$.

Lemma 4.7. For $n = 3$, $w, q\in V(xQ_3)$ and $w$ is adjacent to $q$, $w', q'$ are the external neighbors of $w$ and $q$ respectively. There exist $2$ internally vertex-disjoint paths of length odd, joining $w'$ and $q'$.

Proof. Without loss of generality, suppose $x = 000$, $w = (x, z), q = (x, z_1)$, and $z_1$ differs from $z$ in the first bit. We consider the following cases by the value of $d_{H}(x, z)$.

Case 1. $d_{H}(x, z) = 0$.

That is $z = 000$, then $d_{H}(x, z_1) = 1$. Let $z_1 = 001$. $w = (000,000), q = (000,001)$, $w' = (111,111), q' = (001,000)$ are the external neighbor of $w$ and $q$ respectively. There are two internally vertex-disjont paths of length $5$ joining $w'$ and $q'$, denoted by $P_1, P_2$, $P_1: (111,111)-(111,110)-(110,111)$$-(110,110)-(001,001)-(001,000)$, $P_2: (111,111)-(111,101)-(101,111)-(101,011)$$-(011,101)-(011,100)-(100,011)-(100,001)- (001,100)-(001,000)$, see Fig. 3.

Case 2. $d_{H}(x, z) = 1$.

Without loss of generality, let $z = 001$, then $d_{H}(x, z_1) = 0$ or $d_{H}(x, z_1) = 2$. If $d_{H}(x, z_1) = 0$, the result can be obtained by Case $1$. Thus $d_{H}(x, z_1) = 2$, let $z_1 = 011$. $w = (000,001), q = (000,011), w' = (001,000), q' = (011,000)$. There are two internally vertex-disjoint paths of length $5$ joining $(001,000)$ and $(011,000)$, denoted by $P_1, P_2$, $P_1: (001,000)-(001,010)-(010,001)$$-(010,011)-(011,010)-(011,000)$, $P_2: (001,000)-(001,100)-(100,001)$$-(100,011)-(011,100)-(011,000)$, see Fig.4.

Case 3. $d_{H}(x, z) = 2$.

Without loss of generality, suppose $z = 011$, then $d_{H}(x, z_1) = 1$ or $d_{H}(x, z_1) = 3$. If $d_{H}(x, z_1) = 1$, we can obtain the result by case $2$. Thus $d_{H}(x, z_1) = 3$, $(x, z) = (000,011)$, and let $(x, z_1) = (000,111)$. $w = (000,011), q = (000,111)$, $w' = (011,000)$ and $q' = (111,000)$. There exist two internally vertex-disjoint $5$-paths joining $w'$ and $q'$, denoted by $P_1, P_2$, $P_1: (011,000)-(011,010)-$$(010,011)-(010,111)-(111,010)-(111,000)$, $P_2: (011,000)-(011,100)-$$(100,011)-(100,111)-(111,100)-(111,000)$, see Fig. 5.

Case 4. $d_{H}(x, z) = 3$.

Then $d_{H}(x, z') = 2$, the proof is similar to case $3$.

Lemma 4.8. For $n\geq 3$, let $w, q\in V(xQ_n)$ and $w$ is adjacent to $q$, $w', q'$ are the external neighbors of $w$ and $q$ respectively. There exist $2$ internally vertex-disjoint paths of length odd, joining $w'$ and $q'$.

Proof. Suppose $w = (x, z), q = (x, z_1)$, $z_1$ differs from $z$ in the first bit. The conclusion holds clearly for $n = 3$ by Lemma 4.7. Assume $n\geq 4$ below. We complete the proof by induction on $n$. Now we suppose the result holds for $n-1$. Then $0\leq d_{H}(x, z)\leq n$. If $0\leq d_{H}(x, z)\leq n-2$, the result can be obtained by induction hypothesis easily. Thus $d_{H}(x, z) = n-1$ or $n$. If $d_{H}(x, z) = n$, then $d_{H}(x, z_1)$ must be $n-1$, , the case is the same as $d_{H}(x, z) = n-1$ and $d_{H}(x, z_1) = n$. Now we suppose $d_{H}(x, z) = n-1$, then $d_{H}(x, z_1) = n-2$ or $n$, the case $d_{H}(x, z_1) = n-2$ holds by induction, thus $d_{H}(x, z_1) = n$. Without loss of generality, suppose $x = 0^n, z = 01^{n-1}, z_1 = 1^n$. $w = (x, z) = (0^n, 01^{n-1}), q = (x, z_1) = (0^n, 1^n)$, their external neighbors are $w' = (01^{n-1}, 0^n)$ and $q' = (1^n, 0^0)$ respectively. We can find two vertex-disjoint paths joining $w'$ and $q'$, denoted by $P_1$ and $P_2$, $P_1: (01^{n-1}, 0^n)-(01^{n-1}, 0^{n-1}1)-(0^{n-1}1, 01^{n-1})$$-(0^{n-1}1, 1^n)-(1^n, 0^{n-1}1)-(1^n, 0^n)$, $P_2: (01^{n-1}, 0^n)-(01^{n-1}, 10^{n-1})-(10^{n-1},$$01^{n-1})-(10^{n-1}, 1^n)-(1^n, 10^{n-1})-(1^n, 0^n)$, see Fig.6.

Theorem 4.9. For $n\geq4$, $mp_1(HCN_n) = 2n$, and it is conditionally super matched.

Proof. By Theorem 4.1, we know that $mp_1(HCN_n) = 2n$. Now we only need to prove that $HCN_n$ is conditionally super matched. Let $|F| = 2n$, it is enough to show that one of the following holds: (1) $HCN_n-F$ has an isolated vertex; (2) $F$ is a conditional matching preclusion set; (3) $HCN_n-F$ has a perfect matching. We use the same notation as in the proof of Theorem 4.1. As $|F_1|\geq{n}$, $|F_c|\geq 1$, then $|F_j|\leq{n-1}$ for $j\in \{2, \ldots, 2^n\}$. We claim that $|F_c|\leq n$. If $|F_c|\geq{n+1}$, then $|F_i|\leq{n-1}$ for each $i(1\leq i\leq 2^n)$, thus $x^iQ_n-F_i$ has a perfect matching, say $M_i$, the $M = \cup^{2n}_{i = 1}M_i$ is a perfect matching of $HCN_n-F$. We consider the following cases.

Case 1. $2\leq|F_c|\leq{n}$, then $n\leq|F_1|\leq2n-2$.

If $xQ_n-F_1$ has an isolated vertex, say $u$. Let $u_i'$ be the external neighbors of $u_i, (i = 1, 2, \cdots, n)$. And $(u, u')\notin{F}$, otherwise $u$ is an isolated vertex in $xQ_n-F$. Let $|F_c| = \ell(\ell\geq 2)$, then $|F_1|\leq 2n-\ell$, and $|F_1\cap E(xQ_n-u)|\leq n-\ell$. As $xQ_n-u$ consists of $n$ edge-disjoint almost perfect matchings, $xQ_n-u$ has at least $\ell$ edge-disjoint almost perfect matchings. Suppose the $\ell$ vertices unmatched are $u_1, u_2, \cdots, u_{\ell}$. By corollary 2.5, there are $\ell$ paths $P'_1, P'_2, \ldots, P'_{\ell}$. If there is $P'_i(1\leq i\leq \ell)$ such that none of crossing edge of $E(P'_i)$ is in $F_c$, say $P'_1$, we can also find a perfect matching of $HCN_n-F$. If for each $P'_i(1\leq i\leq \ell)$, one crossing edge of $E(P'_i)$ is in $F_c$. From Lemma 4.5, there is an almost perfect matching such that a vertex $v$ with $d(u, v) = 3$ is unmatched. From Lemma 4.6, there is a cycle $L$ of even order and $V(L)$ contains $u, v$. The perfect matching induced by $L$ is denoted by $M_L$, and $xQ_n-(F_1\cup (V(L)\cap V(xQ_n)))$ has a perfect matching, say $M_{x^1}$, $\cup_{i = 2}^{2^n}xQ_n-(V(L)-(V(L)\cap V(xQ_n)))$ also has a perfect matching, say $M'$, then $M = M_L\cup M_{x^1}\cup M'$ is a perfect matching of $HCN_n-F$.

If $xQ_n-F_1$ has no isolated vertex, then $F_1$ is a conditional super matching preclusion set of $xQ_n-F_1$ with $|F_1| = 2n-2$ and $|F_c|\leq 2$. We may assume that it is induced by $u_1-u-u_2$. Let $u, v_1, \cdots, v_{n-1}$ be the neighbors of $u_1$ in $xQ_n$, and $u, w_1, \cdots, w_{n-1}$ be the neighbors of $u_2$ in $xQ_n$, ${v_i}'$, ${w_i}'$ be the external neighbor of $v_i$ and $w_i(i = 1, 2, \ldots, n-1)$ respectively. There is at least one of $\{(u_1, u'_1), (u_2, u'_2)\}$ not in $F_c$, otherwise, $F$ is a conditional super matching preclusion, say $(u_1, u'_1)\notin{F}$. By Corollary 2.5, there are $n-1$ internally vertex-disjoint $7$-paths joining $u_1'$ and $\{v_1, \ldots, v_{n-1}\}$, say $Q_1, \ldots, Q_{n-1}$. As $|F_c|\geq 2$, $|F_c| = 2$. And $n\geq 4$, there is at least one path $Q_i(i = 1, 2, \ldots, n-1)$ such that none of crossing edge of $E(Q_i)$ is in $F_c$, say $Q_1$. By the proof above, we know that $HCN_n-(V(Q_1)\cup \{u, u_2\}\cup F)$ has a perfect matching, say $M_0$, and $Q_1$ induces a perfect matching, say $M'$. Then $M_0\cup M'\cup (u, u_2)$ is a perfect matching of $HCN_n-F$.

Case 2. $|F_c| = 1$.

If $|F_1|\leq2n-2$, the perfect matching of $HCN_n-F$ can be obtained as the Case 1. Thus we only consider $|F_1| = 2n-1$, and $xQ_n-F_1$ has at most two isolated vertices.

If $xQ_n-F_1$ has two isolated vertices. We can claim that the two isolated vertices are adjacent. Otherwise $|F_1|\geq 2n$ for $\delta(Q_n) = n$, a contradiction. Without loss of generality, suppose such two isolated vertices are $u$ and $u_1$. As both $u$ and $u_1$ are not isolated vertices in $HCN_n-F$, then $(u, u')\notin F_c$ and $(u_1, u_1')\notin F_c$. From Lemma 4.8, there are $2$ internally vertex-disjoint paths of even order joining endpoints $u'$ and $u'_1$, say $R_1, R_2$. As $|F_c| = 1$, there is at least one path $R_i(i = 1, 2)$ such that none of crossing edges of $E(R_i)$ is in $F_c$, say $R_1$. And $HCN_n-(V(R_1)\cup \{u', u'_1\}\cup F)$ has a perfect matching, say $M_0$, $V(R_1)\cup \{u', u'_1\}$ induces a perfect matching, say $M_1$, then $M = M_0\cup M_1$ is a perfect matching of $HCN_n-F$.

If $xQ_n-F_1$ has an isolated vertex. As there are $n$ edge-disjoint almost perfect matchings of $xQ_n-u$, then there exists at least one almost perfect matching of $xQ_n-F_1$, say $M'$, and $u_1$ is unmatched. Moreover, $(u, u')\notin{F_c}$, otherwise $u$ is an isolated vertex of $HCN_n-F$. If $(u_1, {u_1}')\in{F_c}$, as $u_1$ is not an isolated vertex of $xQ_n-F_1$, there exists a vertex adjacent to $u_1$, say $v_1$. Let $v\in V(xQ_n)$, and $(v_1, v)\in M'$, then $d(u, v) = 3$. From Lemma 4.6, there is a cycle $L$ of even order and $V(L)$ contains $u$ and $v$. The perfect matching of $HCN_n-(V(L)\cup F)$ is denoted by $M_0$, and $V(L)$ induces a perfect matching, say $M_1$, then $M = M_0\cup M_1$ is a perfect matching of $HCN_n-F$. If $(u_1, {u_1}')\notin{F_c}$, by the proof case $1$, we can find a perfect matching of $HCN_n-F$ similarly.

If $xQ_n-F_1$ has no isolated vertex. Suppose $f = (u_1, v_1), f' = (u_2, w_1)$, and $f, f'$ are independent, by Lemma 4.2, $xQ_n-(F_1-{f})$ and $xQ_n-(F_1-{f'})$ contain a perfect matching. For $|F_c| = 1$, there is at most one of $\{(u_1, u'_1), (v_1, v'_1), (w, w'), (w_1, {w_1}')\}$ in $F_c$. Without loss of generality, $(u_1, u'_1)\notin{F_c}$, $(v_1, {v_1}')\notin{F_c}$. By the proof of case $1$, we can find a perfect matching of $HCN_n-F$.

5.   Conclusions

Hierarchical cube network is a very important network constructed based on $2^n$ hypercube networks and a perfect matching between them. The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings, and the conditional matching preclusion number of a graph is the minimum number of edges whose deletion leaves a resulting graph with no isolated vertices that has neither perfect matchings nor almost perfect matchings. In this paper, we find these two numbers for the hierarchical cubic network($HCN_n$), characterize all its optimal matching preclusion sets and conditional matching exclusion sets, and prove that the hierarchical cube network has the property of super matching. These results generalize some related results of Birgham et al. ^[1] and E. Cheng et al. ^[4] from hypercube network to hierarchical cubic network.

Acknowledgments

This work was partially supported by the National Natural Science Foundation of China (Nos. 12161073) and the Qinghai Natural Science Foundation of China (Nos. 2020-ZJ-924).

Conflict of interest

The authors declare no conflict of interest.