Structure and substructure connectivity of circulant graphs and hypercubes

T. Tamizh Chelvam can be contacted at: tamche59@gmail.com

Let $H$ be a connected subgraph of a connected graph $G .$ The $H$ -structure connectivity of the graph $G$ ⁠, denoted by $κ (G; H),$ is the minimum cardinality of a minimal set of subgraphs $F = {H_{1}^{'}, H_{2}^{'}, \dots, H_{m}^{'}}$ in $G$ ⁠, such that every ${H^{'}}_{i} \in F$ is isomorphic to $H$ and removal of $F$ from $G$ will disconnect $G$ ⁠. The $H$ -substructure connectivity of the graph $G$ ⁠, denoted by $κ^{s} (G; H),$ is the minimum cardinality of a minimal set of subgraphs $F = {J_{1}^{'}, J_{2}^{'}, \dots, J_{m}^{'}}$ in $G$ ⁠, such that every $J_{i}^{'} \in F$ is a connected subgraph of $H$ and removal of $F$ from $G$ will disconnect $G .$ In this paper, we provide the $H$ -structure and the $H$ -substructure connectivity of the circulant graph Cir $(n, Ω)$ where $Ω = {1, \dots, k, n - k, \dots, n - 1}, 1 \leq k \leq ⌊ \frac{n}{2} ⌋$ and the hypercube $Q_{n}$ for some connected subgraphs $H .$

1. Introduction

A simple graph $G = (V, E)$ is a finite nonempty set $V (G)$ of objects called vertices together with a (possibly empty) set $E (G)$ of unordered pairs of distinct vertices of $G$ called edges. Two distinct vertices $u, v \in V (G)$ are said to be adjacent in $G$ if $u$ and $v$ are connected by an edge and it is represented by ${u, v} \in E (G)$ ⁠. A graph $G$ is said to be trivial if it contains only one vertex and no edges. The connectivity is an important indicator of the reliability and fault tolerability of a network. The vertex connectivity of a connected graph $G$ ⁠, denoted by $κ (G)$ ⁠, is the minimum cardinality of a vertex subset $S \subseteq V (G)$ ⁠, whose removal would disconnect $G$ or $G \ S$ is the trivial graph. As a generalization of the vertex connectivity $κ (G)$ ⁠, Cheng-Kuan Lin et al. [6] introduced two new kinds of connectivity, called structure connectivity and substructure connectivity. A set $F$ of connected subgraphs of a graph $G$ is a subgraph-cut of $G$ if $G \ V (F)$ is a disconnected graph or $K_{1}$ ⁠. Let $H$ be a connected subgraph of $G$ ⁠. Then $F$ is an $H$ -structure cut if $F$ is a subgraph cut, and every element in $F$ is isomorphic to $H$ ⁠. The $H$ -structure connectivity of $G$ ⁠, denoted by $κ (G; H)$ ⁠, is defined to be the minimum cardinality of all $H$ -structure cuts of $G$ ⁠. $F$ is an $H$ -substructure cut if $F$ is a subgraph-cut, and every element in $F$ is isomorphic to a connected subgraph of $H$ ⁠. The $H$ -substructure connectivity of $G$ ⁠, denoted by $κ^{s} (G; H)$ ⁠, is the minimum cardinality of all $H$ -substructure cuts of $G$ ⁠. Since every $H$ -structure cut is an $H$ -substructure cut $κ^{s} (G; H) \leq κ (G; H)$ ⁠. If $H = K_{1}$ then we have $κ (G; H) = κ^{s} (G; H)$ ⁠.

The vertex connectivity $κ (G) \geq κ^{s} (G; H)$ for every subgraph $H$ of $G$ whereas the relation between vertex connectivity and structure connectivity depends on $H$ ⁠. For the graph $G$ ⁠, given in Figure 1, $κ (G) = 2$ ⁠, the structure connectivity of $G$ with respect to the cycle of length $5, κ (G; C_{5}) = 1$ and the structure connectivity of $G$ with respect to the cycle of length $4, κ (G; C_{4}) = 3$ ⁠.

Let $Γ$ be a finite group with $e$ as the identity. A generating set of $Γ$ is a subset $Ω$ such that every element of $Γ$ can be expressed as a product of finitely many elements in $Ω$ ⁠. Assume that $e \notin Ω$ and $a \in Ω$ implies $a^{- 1} \in Ω$ and such a subset $Ω$ is called as a symmetric generating set of $Γ$ ⁠. Hereafter, we assume that $Ω$ is a symmetric generating set of a finite group $Γ$ ⁠. A Cayley graph is a graph $G = (V, E)$ ⁠, where $V (G) = Γ$ and two vertices $x$ and $y$ are adjacent if $x y^{- 1} \in Ω$ and it is denoted by Cay $(Γ, Ω)$ ⁠. The inclusion of the inverse in $Ω$ for every element of $Ω$ means that Cay $(Γ, Ω)$ is undirected. Since $Ω$ is a generating set for $Γ$ ⁠, Cay $(Γ, Ω)$ is connected and Cay $(Γ, Ω)$ is a regular graph of degree $| Ω |$ ⁠. Cayley graphs are extensively dealt in the literature and various authors including Dejter [3], Lakshmivarahan [4], Lee [5], Tamizh Chelvam [8], and Wang [10] have worked on Cayley graphs. For example, one can refer the survey by Tamizh Chelvam and Sivagami [9] for domination in Cayley graphs. The Cayley graph constructed out of the finite cyclic group $ℤ_{n}, n \geq 2$ along with a symmetric generating set $Ω$ is called a circulant graph and the same is denoted by Cir $(n, Ω)$ ⁠. The hypercube $Q_{n}$ is the Cayley graph defined on the group $ℤ_{2}^{n}$ with the standard orthonormal basis as the generating set. Cheng-Kuan Lin et al. [6] have obtained $κ (Q_{n}; H)$ and $κ^{s} (Q_{n}; H)$ for $H \in {K_{1}, K_{1,1}, K_{1,2}, K_{1,3}, C_{4}}$ ⁠. Here, we provide an example in Figure 2, to exhibit a structure cut of the circulant graph Cir $(10, {1,2,3,7,8,9})$ with respect to $K_{3}$ ⁠. In Figure 2, the structure cut is indicated by the dotted lines and note that $κ^{s} (C i r (10, {1,2,3,7,8,9}; K_{3})) = 2$ ⁠.

Throughout this paper, $G - X$ denotes the removal of a set $X$ of subgraphs from the graph $G$ and $G \ B$ denotes the removal of the set $B \subseteq V (G)$ from the graph $G$ ⁠. When $X = {H}$ ⁠, $G - X$ is simply denoted as $G - H$ ⁠. For a graph $G$ ⁠, the open neighborhood $N (v)$ of a vertex $v \in V (G)$ is the set of all vertices which are adjacent to $v$ ⁠. The closed neighborhood of $v$ is $N [v] = N (v) \cup {v}$ ⁠. Let $G_{1} = (V_{1}, E_{1})$ and $G_{2} = (V_{2}, E_{2})$ be two graphs. Then the intersection of $G_{1}$ and $G_{2}$ ⁠, denoted by $G_{1} \cap G_{2}$ ⁠, is the graph whose vertex set is $V_{1} \cap V_{2}$ and the edge set is $E_{1} \cap E_{2}$ ⁠. The union of two disjoint vertex sets graphs $G_{1} = (V_{1}, E_{1})$ and $G_{2} = (V_{2}, E_{2})$ ⁠, denoted by $G_{1} \cup G_{2}$ ⁠, is the graph whose vertex set is $V_{1} \cup V_{2}$ and the edge set is $E_{1} \cup E_{2}$ ⁠. For basic definitions and properties related to graph theory, one can refer [2]. For undefined definitions related to algebraic graph theory, one can refer [1].

In Section 2, we obtain the $H$ -structure and the $H$ -substructure connectivity of the circulant graph Cir $(n, Ω)$ where $Ω = {1, \dots, k, n - k, \dots, n - 1}$ ⁠, for $1 \leq k \leq ⌊ \frac{n}{2} ⌋$ with respect to some of its connected subgraphs. For integers $n (\geq 5)$ and $m$ with $2 \leq m \leq n - 2$ ⁠, Mane [7] proved that $κ (Q_{n}; C_{k}) \leq n - m$ ⁠, where $k$ is a positive even integer with $2^{m} < k < 2^{m + 1}$ and observed that $κ (Q_{4}; C_{6}) = 2$ ⁠. In Section 3, for $n \geq 4$ ⁠, we obtain the exact value for $κ (Q_{n}; C_{6})$ ⁠.

2. Structure and substructure connectivity of circulant graphs

Throughout this section $n (\geq 2)$ ⁠, $m$ and $k$ are integers such that $1 \leq k \leq ⌊ \frac{n}{2} ⌋$ and $Ω = {1,2, \dots, k, n - k, \dots, n - 1}$ ⁠. We take the elements of $ℤ_{n}$ as $ℤ_{n} = {0,1, \dots, n - 1}$ ⁠. The following result due to Wang [10] is useful in the paper.

Theorem 2.1

([10, Wang]). Let $n$ and $k$ be positive integers such that $1 \leq k \leq ⌊ \frac{n}{2} ⌋$ , $Ω = {1, \dots, k, n - k, \dots, n - 1}$ and $G = Cir (n, Ω)$ . Then $κ (G) = | Ω |$ .

By definition and from Theorem 2.1, we have the following corollary.

Corollary 2.2.

Let $n (\geq 2)$ and $k$ be positive integers such that $1 \leq k \leq ⌊ \frac{n}{2} ⌋$ , $Ω = {1, \dots, k, n - k, \dots, n - 1}$ and $G = Cir (n, Ω)$ . Then $κ (G; K_{1}) = | Ω |$ and $κ^{s} (G; K_{1}) = | Ω |$ .

A star graph $K_{1, m} (m \geq 1)$ is a complete bipartite graph comprised of two partite sets of vertices of sizes $1$ and $m$ respectively, such that two vertices are adjacent if and only if they are in different partite sets. If $K_{1, m}$ is a subgraph of Cir $(n, Ω)$ ⁠, then $m \leq | Ω |$ ⁠. If $k = ⌊ \frac{n}{2} ⌋$ and $Ω = {1, \dots, k, n - k, \dots, n - 1}$ ⁠, then the circulant graph $G = Cir (n, Ω)$ is the complete graph $K_{n}$ ⁠. Now, we obtain the structure connectivity of $K_{n}$ ⁠, as a circulant graph with respect to $K_{1, m}$ ⁠. If $m + 1$ does not divide $n - 1$ ⁠, then removal of $λ K_{1, m}$ does not disconnect Cir $(n, Ω)$ for any $λ$ ⁠. Hence the structure connectivity of $K_{n}$ with respect to $K_{1, m}$ is meaningful only when $m + 1$ divides $n - 1$ ⁠.

Lemma 2.3.

Let $n (\geq 2)$ and $k$ be positive integers such that $k = ⌊ \frac{n}{2} ⌋$ , $Ω = {1, \dots, k, n - k, \dots, n - 1}$ and $G = Cir (n, Ω)$ . For a positive integer $m$ with $m \leq n - 2$ , $κ^{s} (G; K_{1, m}) = ⌈ \frac{n - 1}{m + 1} ⌉$ . Also, $κ (G; K_{1, m}) = \frac{n - 1}{m + 1}$ if $m + 1$ divides $n - 1$ .

Proof.

By the assumption on $n, k$ and $Ω$ ⁠, Cir $(n, Ω) = K_{n}$ ⁠. By Theorem 2.1, $G$ is $(n - 1)$ - connected. Let $F$ be a $K_{1, m}$ -substructure cut with minimum cardinality of $G = Cir (n, Ω)$ ⁠. Suppose $κ^{s} (G; K_{1, m}) < ⌈ \frac{n - 1}{m + 1} ⌉$ ⁠. Then $| V (F) | < n - 1$ and $G \ V (F)$ is disconnected, which is a contradiction to $G$ is $(n - 1)$ -connected. Hence $κ^{s} (G; K_{1, m}) \geq ⌈ \frac{n - 1}{m + 1} ⌉$ ⁠.

For $1 \leq i \leq ⌈ \frac{n - 1}{m + 1} ⌉ - 1$ ⁠, let $H_{i}$ be the subgraph of $G$ with $i (m + 1)$ as the central vertex and $i (m + 1) - 1, \dots, i (m + 1) - m$ as the end vertices and hence isomorphic to $K_{1, m}$ ⁠. Consider the subgraph $H_{⌈ \frac{n - 1}{m + 1} ⌉}$ of $G$ with $(n - 1)$ as the central vertex and all remaining vertices of $(G - {H_{1}, \dots, H_{⌈ \frac{n - 1}{m + 1} ⌉ - 1}}) \ {0, n - 1}$ as end vertices. Note that $H_{⌈ \frac{n - 1}{m + 1} ⌉}$ is isomorphic to a subgraph of $K_{1, m}$ ⁠. Clearly $G - {H_{1}, \dots, H_{⌈ \frac{n - 1}{m + 1} ⌉}}$ is the trivial graph $K_{1}$ ⁠. Hence $κ^{s} (G; K_{1, m}) \leq ⌈ \frac{n - 1}{m + 1} ⌉$ ⁠. Thus $κ^{s} (G; K_{1, m}) = ⌈ \frac{n - 1}{m + 1} ⌉$ ⁠.

Suppose $m + 1$ divides $n - 1$ ⁠. As mentioned above in the proof, $H_{\frac{n - 1}{m + 1}}$ is a subgraph of $G$ isomorphic to $K_{1, m}$ and so $κ (G; K_{1, m}) \leq \frac{n - 1}{m + 1}$ ⁠. Now $\frac{n - 1}{m + 1} = κ^{s} (G; K_{1, m}) \leq κ (G; K_{1, m}) \leq \frac{n - 1}{m + 1}$ ⁠. Hence $κ (G; K_{1, m}) = \frac{n - 1}{m + 1}$ ⁠. □

In Lemma 2.3, we have considered $k = ⌊ \frac{n}{2} ⌋$ in which case $G = Cir (n, Ω)$ is complete. Now, we consider $k < ⌊ \frac{n}{2} ⌋$ ⁠, so that $G = Cir (n, Ω)$ can never be complete. By considering $k < ⌊ \frac{n}{2} ⌋$ ⁠, we determine the structure and substructure connectivity of Cir $(n, Ω)$ with respect to $K_{1, m}$ where $m \leq 2 k$ ⁠.

Theorem 2.4.

Let $n (\geq 4), k$ and $m$ be positive integers such that $1 \leq k < ⌊ \frac{n}{2} ⌋$ and $m \leq 2 k$ . Let $Ω = {1, \dots, k, n - k, \dots, n - 1}$ and $G = Cir (n, Ω)$ . Then the following are equivalent:

(i) $κ^{s} (G; K_{1, m}) = 1;$
(ii) $m + 1 = 2 k + 1 = n - 1;$
(iii) $κ (G; K_{1, m}) = 1$ .

Proof.

Since $k < ⌊ \frac{n}{2} ⌋$ ⁠, $| Ω | = 2 k < n - 1$ ⁠.

(i) $\Rightarrow$ (ii). Assume that $κ^{s} (G; K_{1, m}) = 1$ ⁠. So that there exists a subgraph $K_{1, t}$ of $K_{1, m}$ for some $t, t \leq m \leq 2 k$ such that $G - K_{1, t}$ is disconnected or a trivial graph. Since $G$ is vertex transitive, one can have the central vertex of $K_{1, t}$ as $u = 0$ ⁠. Consider the subgraph $H$ of $G$ induced by 〈 ${0, \pm 1, \dots, \pm k}$ 〉. The graph $G - H$ is connected and the vertices of $H$ other than $0$ are adjacent to either $k + 1$ or $n - (k + 1)$ in $G$ ⁠. Note that $G - H$ is a subgraph of $G - K_{1, t}$ ⁠. Suppose $t < 2 k$ ⁠, then $G - K_{1, t}$ is connected, which is a contradiction. Hence $t = m = 2 k$ and $G - K_{1, t} = G - K_{1,2 k}$ ⁠. It is easy to observe that the graphs $G - K_{1,2 k}$ and $G - H$ are equal. It is known that $m = 2 k \leq n - 2$ ⁠. Suppose $2 k < n - 2$ ⁠, then $G - K_{1, t} = G - H$ is connected, which is a contradiction. This implies that $t = m = 2 k = n - 2$ ⁠. Hence $m + 1 = 2 k + 1 = n - 1$ ⁠.

(ii) $\Rightarrow$ (iii). Assume that $m + 1 = 2 k + 1 = n - 1$ ⁠. For $u \in V (G)$ ⁠, deg $(u) = 2 k = n - 2$ and hence $G \ N [u] = K_{1}$ ⁠. Since $| N (u) | = 2 k = m$ ⁠, $K_{1, m}$ is a subgraph of $〈 N [u] 〉$ and hence removal of $〈 N [u] 〉$ from $G$ is same as removing $K_{1, m}$ from $G$ ⁠. Thus $κ (G; K_{1, m}) = 1$ ⁠.

(iii) $\Rightarrow$ (i). Since $κ^{s} (G; K_{1, m}) \leq κ (G; K_{1, m}) = 1$ ⁠, $κ^{s} (G; K_{1, m}) = 1$ ⁠. □

Remark 2.5.

Let $n (\geq 6)$ and $k$ be positive integers such that $2 \leq k < ⌊ \frac{n}{2} ⌋$ ⁠, $Ω = {1, \dots, k, n - k, \dots, n - 1}$ ⁠, $G = Cir (n, Ω)$ and $m \leq 2 k$ ⁠. Even without the condition $n > (m + 1) ⌈ \frac{2 k}{m + 1} ⌉$ ⁠, one can talk about $κ^{s} (G; K_{1, m})$ ⁠, whereas it is not so in the case of $κ (G; K_{1, m})$ ⁠. For, if $n \leq (m + 1) ⌈ \frac{2 k}{m + 1} ⌉$ ⁠, then for any integer $λ$ with $| V (λ K_{1, m}) | \leq n$ ⁠, removal of $λ K_{1, m}$ does not disconnect $G$ ⁠.

Consider $n \leq (m + 1) ⌈ \frac{2 k}{m + 1} ⌉$ ⁠. If $λ < ⌈ \frac{2 k}{m + 1} ⌉$ ⁠, then $| V (λ K_{1, m}) | < 2 k$ and hence by Theorem 2.1, $G$ is connected after removal of $λ K_{1, m}$ from $G$ ⁠. On the other hand if $λ \geq ⌈ \frac{2 k}{m + 1} ⌉$ ⁠, then $| V (λ K_{1, m}) | \geq (m + 1) ⌈ \frac{2 k}{m + 1} ⌉ \geq n$ ⁠. This along with $| V (λ K_{1, m}) | \leq n$ yields $| V (λ K_{1, m}) | = n$ ⁠. Thus $G = λ K_{1, m}$ ⁠.

Now, we attempt to obtain $κ (C i r (n, Ω); K_{1, m})$ and $κ^{s} (Cir (n, Ω); K_{1, m})$ ⁠, for $2 \leq m + 1 \leq k$ and $Ω = {1, \dots, k, n - k, \dots, n - 1}$ ⁠.

Theorem 2.6.

Let $n (\geq 6)$ and $k$ be positive integers such that $2 \leq k < ⌊ \frac{n}{2} ⌋$ , $Ω = {1, \dots, k, n - k, \dots, n - 1}$ and $G = Cir (n, Ω)$ . If $m$ is an integer such that $2 \leq m + 1 \leq k$ and $(m + 1) ⌈ \frac{2 k}{m + 1} ⌉ < n$ , then $κ (G; K_{1, m}) = ⌈ \frac{2 k}{m + 1} ⌉$ and $κ^{s} (G; K_{1, m}) = ⌈ \frac{2 k}{m + 1} ⌉$ .

Proof.

Let $a_{i} = n - (k - i + 1)$ for $1 \leq i \leq k$ ⁠, $a_{i} = i - k$ for $k + 1 \leq i \leq 2 k$ and $b_{j} = j$ for $k + 1 \leq j \leq n - (k + 1)$ ⁠. By division algorithm $2 k = (m + 1) s + r$ and $k = (m + 1) h + r^{'}$ for some $r$ and $r^{'}$ with $0 \leq r \leq m$ and $0 \leq r^{'} \leq m$ ⁠.

For $1 \leq i \leq s = \frac{2 k - r}{m + 1}$ ⁠, let $H_{i}$ be defined as follows.

$V (H_{i}) = {a_{(m + 1) i - m}, a_{(m + 1) i - (m - 1)}, \dots, a_{(m + 1) i}}$ and edge set

E (H_{i}) = {{a_{(m + 1) i - (m - r^{'})}, a_{(m + 1) i - (m - j)}} : j \in {0, \dots, m} / {r^{'}}} .

Further when $r \neq 0$ ⁠, let $H_{s + 1}$ be defined as follows.

$V (H_{s + 1}) = {v_{1}, \dots, v_{m + 1} : v_{i} = {\begin{array}{l} a_{2 k - (r - i)} & if 1 \leq i \leq r \\ b_{k + i - r} & if r + 1 \leq i \leq m + 1 \end{array}}$ and edge set

E (H_{s + 1}) = {{v_{r^{'} + 1}, v_{j}} : j \in {1, \dots, m + 1} \ {r^{'} + 1}} .

In $G$ ⁠, two vertices $u$ and $v$ are adjacent if and only if $u, v \in ℤ_{n}$ has the property that $| u - v | \leq k$ ⁠. Since $| a_{(m + 1) i - (m - r^{'})} - a_{(m + 1) i - (m - j)} | \leq k$ for every $0 \leq j \leq m$ and $| v_{r^{'} + 1} - v_{j} | \leq k$ for every $1 \leq j \leq m + 1$ ⁠, $H_{i}$ is indeed a subgraph of $G$ for every $1 \leq i \leq s + 1$ ⁠.

Note that, each $H_{i}$ is isomorphic to $K_{1, m}$ ⁠. Let $H$ be the union of subgraphs given by $H = {\begin{matrix} ⋃_{i = 1}^{s} H_{i} = ⋃_{i = 1}^{s} K_{1, m} & if r = 0; \\ ⋃_{i = 1}^{s + 1} H_{i} = ⋃_{i = 1}^{s + 1} K_{1, m} & if r \neq 0. \end{matrix}$

Note that $V (H) = ⌈ \frac{2 k}{m + 1} ⌉ K_{1, m}$ ⁠, $N (0) \subseteq V (H)$ ⁠, $G - H$ is disconnected with ${0}$ as one component. Thus, $κ (G; K_{1, m}) \leq ⌈ \frac{2 k}{m + 1} ⌉$ and so $κ^{s} (G; K_{1, m}) \leq ⌈ \frac{2 k}{m + 1} ⌉$ ⁠. By Theorem 2.1, $G$ is $2 k$ -connected. Suppose there exists a set $F^{'} = {H_{1}^{'}, \dots, H_{t}^{'}}$ of subgraphs of $G$ such that every $H_{i}^{'} \in F^{'}$ is isomorphic to a subgraph of $K_{1, m}$ ⁠, $t < ⌈ \frac{2 k}{m + 1} ⌉$ and $G - F^{'}$ is disconnected. Let $X = V (F^{'})$ ⁠. Clearly $| X | < 2 k$ and by the assumption $G \ X$ is disconnected, which is a contradiction to $G$ is $2 k$ -connected.

Thus $κ^{s} (G; K_{1, m}) \geq ⌈ \frac{2 k}{m + 1} ⌉$ and so $κ (G; K_{1, m}) \geq ⌈ \frac{2 k}{m + 1} ⌉$ ⁠. Hence $κ (G; K_{1, m}) = κ^{s} (G; K_{1, m}) = ⌈ \frac{2 k}{m + 1} ⌉$ ⁠. □

Now we obtain $κ (Cir (n, Ω); K_{1, m})$ and $κ^{s} (Cir (n, Ω); K_{1, m})$ ⁠, for $k < m + 1 \leq 2 k + 1$ and $Ω = {1, \dots, k, n - k, \dots, n - 1}$ ⁠.

Lemma 2.7.

Let $n (\geq 6)$ and $k$ be positive integers such that $2 \leq k < ⌊ \frac{n}{2} ⌋$ , $Ω = {1, \dots, k, n - k, \dots, n - 1}$ and $G = Cir (n, Ω)$ . If $m$ is an integer with $k < m + 1 \leq 2 k + 1$ and $n > (m + 1) ⌈ \frac{2 k}{m + 1} ⌉$ , then

κ (G; K_{1, m}) = κ^{s} (G; K_{1, m}) = {\begin{array}{l} 1 & i f m + 1 = 2 k + 1 = n - 1; \\ 2 & o t h e r w i s e . \end{array}

Proof.

By Theorem 2.6, $κ (G; K_{1, m}) = κ^{s} (G; K_{1, m}) = 2$ for $m + 1 = k$ ⁠. This gives that $κ (G; K_{1, m}) \leq 2$ and so $κ^{s} (G; K_{1, m}) \leq 2$ when $k < m + 1 \leq 2 k + 1$ ⁠. By Theorem 2.4, $κ (G; K_{1, m}) = 1 = κ^{s} (G; K_{1, m})$ if and only if $m + 1 = 2 k + 1 = n - 1$ ⁠. Hence for the other cases $κ (G; K_{1, m}) \geq 2$ and $κ^{s} (G; K_{1, m}) \geq 2$ ⁠. Thus,

κ (G; K_{1, m}) = κ^{s} (G; K_{1, m}) = {\begin{array}{l} 1 & if m + 1 = 2 k + 1 = n - 1; \\ 2 & otherwise . □ \end{array}

Now we provide an example for the $K_{1,4}$ -substructure connectivity of the circulant graph Cir $(16, {1,2,14,15})$ in Figure 3. Here $n = 16, k = 2, m = 4$ and $k < m + 1$ ⁠. The substructure cut is $F = {H_{1} ≅ K_{1,3}, H_{2} ≅ K_{1,2}}$ ⁠. In Figure 3, the substructure cut $F$ is indicated by the dotted lines.

3. Structure and substructure connectivity of hypercubes

The $n$ -dimensional hypercube $Q_{n}$ is the Cayley graph defined on the group $ℤ_{2}^{n}$ with generating set as the standard orthonormal basis. Note that $Q_{n}$ contains $2^{n}$ vertices and $n 2^{n - 1}$ edges. Actually two distinct vertices $x = (x_{1} x_{2} \dots x_{n})$ and $y = (y_{1} y_{2} \dots y_{n})$ in $V (Q_{n})$ are adjacent if and only if $x_{i} \neq y_{i}$ for exactly one $i$ (⁠ $1 \leq i \leq n$ ⁠). For any vertex $x = (x_{1} x_{2} \dots x_{n})$ in $Q_{n}$ ⁠, let ${(x)}^{i} = (x_{1}^{i} x_{2}^{i} \dots x_{n}^{i})$ where $x_{j}^{i} = x_{j}$ for every $j \neq i$ and $x_{i}^{i} = 1 - x_{i}$ ⁠. Note that ${{(x)}^{i}}_{1 \leq i \leq n}$ is the neighborhood set of $x$ in $Q_{n}$ ⁠. For each $t = 0,1$ ⁠, we have two $(n - 1)$ -dimensional subgraphs $Q_{n}^{t}$ of $Q_{n}$ where $V (Q_{n}^{t}) = {x | x = (x_{1} x_{2} \dots x_{n}) \in V (Q_{n}) a n d x_{n} = t}$ and $E (Q_{n}^{t}) = {{x, y} | {x, y} \in E (Q_{n}) a n d x, y \in V (Q_{n}^{t})}$ ⁠. Obviously, $Q_{n}^{t}$ is isomorphic to $Q_{n - 1}$ for each $t = 0,1$ ⁠. The path $P_{m}$ of length $m$ is a walk with $m + 1$ distinct vertices and $m$ distinct edges. The cycle $C_{m}$ of length $m$ is a closed path that contains $m$ distinct vertices.

Cheng-Kuan Lin et al. [6] proved the following theorem for the substructure connectivity of hypercube $Q_{n}$ with respect to the cycle $C_{4}$ ⁠.

Theorem 3.1

([6, Theorem 10]). For $n \geq 4$ ⁠, $κ^{s} (Q_{n}; C_{4}) = ⌈ \frac{n}{2} ⌉$ ⁠.

For integers $n (\geq 5), k$ and $m$ with $k$ is a positive even integer, $2^{m} < k < 2^{m + 1}$ and $2 \leq m \leq n - 2$ ⁠, Mane [7] considered the substructure connectivity of $Q_{n}$ with respect to the cycle $C_{6}$ ⁠. In fact Mane [7] proved that $κ (Q_{n}; C_{k}) \leq n - m$ ⁠, and $κ (Q_{4}; C_{6}) = 2$ ⁠. In this section, for $n \geq 4$ ⁠, we obtain the exact value for $κ (Q_{n}; C_{6})$ ⁠.

First, we obtain the structure connectivity and the substructure connectivity of hypercube $Q_{n}$ with respect to $P_{3}$ ⁠, the path of length 3.

Corollary 3.2.

For $n \geq 4$ , $κ (Q_{n}; P_{3}) = κ^{s} (Q_{n}; P_{3}) = ⌈ \frac{n}{2} ⌉$ .

Proof.

By Theorem 3.1, $κ^{s} (Q_{n}; C_{4}) = ⌈ \frac{n}{2} ⌉$ ⁠. Since all subgraphs of $P_{3}$ are also subgraphs of $C_{4}$ ⁠, we have $κ^{s} (Q_{n}; P_{3}) \geq ⌈ \frac{n}{2} ⌉$ ⁠.

For $1 \leq i \leq ⌈ \frac{n}{2} ⌉ - 1$ ⁠, consider the paths of length $3$ ⁠, $R_{i} : (a_{i 1} \dots a_{i n}) - (b_{i 1} \dots b_{i n}) - (c_{i 1} \dots c_{i n}) - (d_{i 1} \dots d_{i n})$ where

a_{i j} = {\begin{array}{l} 1 & if j = 2 i - 1; \\ 0 & otherwise . \end{array}

b_{i j} = {\begin{array}{l} 1 & if j = 2 i - 1,2 i; \\ 0 & otherwise . \end{array}

c_{i j} = {\begin{array}{l} 1 & if j = 2 i; \\ 0 & otherwise . \end{array}

d_{i j} = {\begin{array}{l} 1 & if j = 2 i, 2 i + 1; \\ 0 & otherwise . \end{array}

For odd $n$ ⁠, let $R_{⌈ \frac{n}{2} ⌉} : (0 \dots 01) - (10 \dots 01) - (10 \dots 011) - (10 \dots 010)$ and for even $n$ ⁠, let $R_{⌈ \frac{n}{2} ⌉} : (0 \dots 010) - (0 \dots 011) - (0 \dots 01) - (10 \dots 01)$ ⁠. The removal of these paths $R_{i}$ ⁠, for $1 \leq i \leq ⌈ \frac{n}{2} ⌉$ ⁠, of length $3$ disconnects $Q_{n}$ with $(0 \dots 00)$ as an isolated vertex. Hence $κ (Q_{n}; P_{3}) \leq ⌈ \frac{n}{2} ⌉$ ⁠.

Thus, we have $⌈ \frac{n}{2} ⌉ \leq κ^{s} (Q_{n}; P_{3}) \leq κ (Q_{n}; P_{3}) \leq ⌈ \frac{n}{2} ⌉$ and so $κ (Q_{n}; P_{3}) = κ^{s} (Q_{n}; P_{3}) = ⌈ \frac{n}{2} ⌉$ ⁠. □

In the following lemma, we obtain an upper bound for the structure connectivity of $Q_{n}$ with respect to $C_{6}$ ⁠.

Lemma 3.3.

For $n \geq 3$ , $κ (Q_{n}; C_{6}) \leq ⌈ \frac{n}{3} ⌉$ .

Proof.

By division algorithm, $n = 3 q + r$ ⁠, $0 \leq r \leq 2$ ⁠. For $1 \leq i \leq q$ ⁠, consider the cycles $B_{i}$ of length $6$ given below:

$B_{i} : (a_{i 1} \dots a_{i n}) - (b_{i 1} \dots b_{i n}) - (c_{i 1} \dots c_{i n}) - (d_{i 1} \dots d_{i n}) - (e_{i 1} \dots e_{i n}) - (f_{i 1} \dots f_{i n}) - (a_{i 1} \dots a_{i n})$ where

a_{i j} = {\begin{array}{l} 1 & if j = 3 i - 2; \\ 0 & otherwise; \end{array}

b_{i j} = {\begin{array}{l} 1 & if j = 3 i - 2 or 3 i - 1; \\ 0 & otherwise; \end{array}

c_{i j} = {\begin{matrix} 1 & if j = 3 i - 1; \\ 0 & otherwise; \end{matrix}

d_{i j} = {\begin{array}{l} 1 & if j = 3 i - 1 or 3 i; \\ 0 & otherwise; \end{array}

e_{i j} = {\begin{matrix} 1 & if j = 3 i; \\ 0 & otherwise; \end{matrix}

f_{i j} = {\begin{array}{l} 1 & if j = 3 i - 2 or 3 i; \\ 0 & otherwise . \end{array}

If $r = 1$ ⁠, let $B_{q + 1} : (0 \dots 001) - (0 \dots 011) - (0 \dots 0111) - (0 \dots 01111) - (00 \dots 01101) - (0 \dots 01001) - (00 \dots 001)$ ⁠.

If $r = 2$ ⁠, let $B_{q + 1} : (0 \dots 010) - (0 \dots 0110) - (0 \dots 0111) - (0 \dots 0101) - (0 \dots 001) - (0 \dots 011) - (00 \dots 010)$ ⁠.

The removal of cycles $B_{1}, B_{2}, \dots, B_{⌈ \frac{n}{3} ⌉}$ disconnects $Q_{n}$ with $(0 \dots 00)$ as an isolated vertex. Hence $κ (Q_{n}; C_{6}) \leq ⌈ \frac{n}{3} ⌉$ ⁠. □

For each $n \geq 3$ ⁠, $Z_{6}^{n}$ is a collection of $6$ -cles of $Q_{n}$ and the same is taken as ${{u, v, w, x, y, z} | {u, v}, {v, w}, {w, x}, {x, y}, {y, z}, {z, u} \in E (Q_{n})}$ ⁠. Let $Z_{6}^{n} = {X_{1}, \dots, X_{m}}$ be a subset of collection of $6$ -cycles of $Q_{n}$ ⁠. For $i = 0,1$ ⁠, ${(Z_{6}^{n})}_{i} \subseteq Z_{6}^{n}$ is the subgraph $⋃_{j = 1}^{m} X_{j} \cap Q_{n}^{i}$ of $Q_{n}$ ⁠. Cheng-Kuan Lin et al. [6] obtained the substructure connectivity of hypercube $Q_{n}$ with respect to $K_{1,2}$ and the same the stated below to obtain a lower bound for the substructure connectivity of the hypercube with respect to $C_{6}$ ⁠.

Lemma 3.4

([6, Theorem 6]). For $n \geq 3$ ⁠, $κ (Q_{n}; K_{1,2}) = ⌈ \frac{n}{2} ⌉$ ⁠.

Lemma 3.5.

If $| Z_{6}^{4} | < 2$ ⁠, then $Q_{4} - Z_{6}^{4}$ is connected.

Proof.

If $| Z_{6}^{4} | = 0$ ⁠, then $Q_{4} - Z_{6}^{4} = Q_{4}$ ⁠, hence is connected. Assume that $| Z_{6}^{4} | = 1$ and $Z_{6}^{4} = {C : u_{1} - u_{2} - u_{3} - u_{4} - u_{5} - u_{6} - u_{1}}$ ⁠.

Suppose $u_{i} \in Q_{4}^{0}$ for all $1 \leq i \leq 6$ ⁠. Since $Q_{4}^{1}$ is connected and every vertex of $Q_{4}^{0} - Z_{6}^{4}$ is connected to a vertex in $Q_{4}^{1}$ ⁠, we get that $Q_{4} - Z_{6}^{4}$ is connected.

If $u_{i} \in Q_{4}^{1}$ for all $1 \leq i \leq 6$ ⁠, then by similar arguments as above, $Q_{4} - Z_{6}^{4}$ is connected.

Assume that $V (C) \cap V (Q_{4}^{0}) \neq φ$ and $V (C) \cap V (Q_{4}^{1}) \neq φ$ ⁠. Without loss of generality one can assume that $| V (C) \cap V (Q_{4}^{0}) | \leq | V (C) \cap V (Q_{4}^{1}) |$ ⁠. Then we have two cases.

Case 1.

Let $| V (C) \cap V (Q_{4}^{0}) | = 2$ and $| V (C) \cap V (Q_{4}^{1}) | = 4$ ⁠. Clearly $Q_{4}^{0} - {(Z_{6}^{4})}_{0}$ is connected and every vertex in $Q_{4}^{1} - {(Z_{6}^{4})}_{1}$ is adjacent to a vertex in $Q_{4}^{0} - {(Z_{6}^{4})}_{0}$ ⁠. Hence $Q_{4} - Z_{6}^{4}$ is connected.

Case 2.

Let $| V (C) \cap V (Q_{4}^{0}) | = 3$ and $| V (C) \cap V (Q_{4}^{1}) | = 3$ ⁠. Note that subgraphs induced by $| V (C) \cap V (Q_{4}^{0}) and$ $| V (C) \cap V (Q_{4}^{1})$ are subgraph isomorphic to $K_{1,2}$ in $Q_{4}^{0}$ and $Q_{4}^{1}$ respectively. Further both $Q_{4}^{0}$ and $Q_{4}^{1}$ are isomorphic to $Q_{3}$ ⁠. By Lemma 3.4, removal of a $K_{1,2}$ does not disconnect $Q_{4}^{0}$ and $Q_{4}^{1}$ ⁠. Thus both $Q_{4}^{0} - {(Z_{6}^{4})}_{0}$ and $Q_{4}^{0} - {(Z_{6}^{4})}_{0}$ are connected. Also there exists a vertex $x \in Q_{4}^{0} - {(Z_{6}^{4})}_{0}$ adjacent to ${(x)}^{4} \in Q_{4}^{1} - {(Z_{6}^{4})}_{1}$ ⁠. Thus $Q_{4} - Z_{6}^{4}$ is connected. □

In the following lemma, we obtain a lower bound for the structure connectivity of $Q_{n}$ with respect to $C_{6}$ ⁠.

Lemma 3.6.

For an integer $n \geq 4$ , $κ (Q_{n}; C_{6}) \geq ⌈ \frac{n}{3} ⌉$ .

Proof.

By induction on $n$ ⁠. By Lemma 3.5, the result is true for $n = 4$ ⁠. Assume as induction hypothesis that the statement holds for $Q_{i}$ ⁠, $4 \leq i \leq n - 1$ ⁠. To complete the proof, one has to prove that if $| Z_{6}^{n} | \leq ⌈ \frac{n}{3} ⌉ - 1$ ⁠, then $Q_{n} - Z_{6}^{n}$ is connected.

Case 1.

Assume that either $V (Z_{6}^{n}) \subseteq V (Q_{n}^{0})$ or $V (Z_{6}^{n}) \subseteq V (Q_{n}^{1})$ ⁠. Without loss of generality, let us assume that $V (Z_{6}^{n}) \subseteq V (Q_{n}^{0})$ ⁠. Note that $Q_{n}^{1}$ is connected and every vertex of $Q_{n}^{0} - Z_{6}^{n}$ is connected to a vertex in $Q_{n}^{1}$ and hence $Q_{n} - Z_{6}^{n}$ is connected.

Case 2.

Suppose $V (Z_{6}^{n}) \cap V (Q_{n}^{1}) \neq φ$ and $V (Z_{6}^{n}) \cap V (Q_{n}^{0}) \neq φ$ ⁠.

Case 2.1.

Assume that, for every 6-cycle $X$ of $Z_{6}^{n}$ ⁠, $V (X) \subset V (Q_{n}^{1})$ or $V (X) \subset V (Q_{n}^{0})$ ⁠. In this case, we have the number of 6-cycles of $Z_{6}^{n}$ and $Q_{n}^{1}$ is at most $⌈ \frac{n}{3} ⌉ - 2$ and $| V (Z_{6}^{n}) \cap V (Q_{n}^{0}) | \leq ⌈ \frac{n}{3} ⌉ - 2$ ⁠. Note that $⌈ \frac{n}{3} ⌉ - 1 \leq ⌈ \frac{n - 1}{3} ⌉$ and so $⌈ \frac{n}{3} ⌉ - 2 < ⌈ \frac{n - 1}{3} ⌉$ ⁠. By the induction hypothesis, $κ (Q_{n}^{i}; C_{6}) \geq ⌈ \frac{n - 1}{3} ⌉$ and thus $Q_{n}^{i} - {(Z_{6}^{n})}_{i}$ is connected for $i \in {0,1}$ ⁠. Since $6 (⌈ \frac{n}{3} ⌉ - 2) < 6 (\frac{n + 3}{3} - 2) = 2 (n - 3) < 2 (n - 2) \leq 2^{n - 2}$ ⁠, for $i = 0,1$ ⁠, $Q_{n}^{i} - {(Z_{6}^{n})}_{i}$ contains more than $\frac{2^{n - 1}}{2}$ vertices. Hence there exists a vertex $u \in Q_{n}^{1} - {(Z_{6}^{n})}_{1}$ which is adjacent to ${(u)}^{n - 1} \in Q_{n}^{0} - {(Z_{6}^{n})}_{0}$ ⁠. Hence $Q_{n} - Z_{6}^{n}$ is connected.

Case 2.2.

Assume that $V (Z_{6}^{n}) \cap V (Q_{n}^{1}) \neq φ$ and $V (Z_{6}^{n}) \cap V (Q_{n}^{0}) \neq φ$ and there is a 6-cycle $X \in Z_{6}^{n}$ such that $V (X) \cap V (Q_{n}^{i}) \neq φ$ for each $i = 0,1$ ⁠.

Let $Z_{6}^{n} = {X_{1}, X_{2}, \dots, X_{m}}$ ⁠, $m \leq ⌈ \frac{n}{3} ⌉ - 1$ where each $X_{i}$ is a 6-cycle. For any $X_{i} \in Z_{6}^{n}$ ⁠, the elements of $V (X_{i})$ differ from one another in at most 3 coordinates. Let us name those coordinates as $k_{i 1}, k_{i 2}, k_{i 3}$ ⁠. i.e., if $0$ (or 1) is the $p$ th coordinate of an element in $V (X_{i})$ for $p \neq k_{i 1}, k_{i 2}, k_{i 3}$ ⁠, then every element of $V (X_{i})$ has $0$ (or $1$ ⁠) as the $p$ th coordinate.

Hence in total we have $3 m$ such coordinates $k_{i 1}, k_{i 2}, k_{i 3}$ ⁠, for $1 \leq i \leq m$ (not necessarily distinct) corresponding to all elements in $Z_{6}^{n}$ ⁠. Further, $3 m \leq 3 ⌈ \frac{n}{3} ⌉ - 3 < 3 (\frac{n + 3}{3}) - 3 = n$ ⁠. Thus there exists $k \in {1,2 \dots, n}$ such that $k \notin {k_{i 1}, k_{i 2}, k_{i 3}}$ for each $1 \leq i \leq m$ ⁠. This means that $k$ th coordinate of $V (X_{i})$ is same in all the 6 elements of $X_{i}$ ⁠. i.e., the $k$ th coordinate of all the elements of $V (X_{i})$ are equal.

Let us partition the vertices of $Q_{n}$ into two subsets $V_{j} = {x = (x_{1} \dots x_{n}) \in V (Q_{n}) : x_{k} = j, k is the index identified above}, j \in {0,1}$ ⁠. By the above arguments, for every $i$ ⁠, $1 \leq i \leq m$ ⁠, either $V (X_{i}) \subseteq V_{0}$ or $V (X_{i}) \subseteq V_{1}$ ⁠. Note that both the induced subgraphs $〈 V_{0} 〉$ and $〈 V_{1} 〉$ of $Q_{n}$ are isomorphic to $Q_{n - 1}$ ⁠. Now, if $Z_{6}^{n} \subseteq V_{j}$ for some $j \in {0,1}$ ⁠, proceeding as in Case 1, $Q_{n} - Z_{6}^{n}$ is connected. Otherwise, proceeding as in Case 2.1, $Q_{n} - Z_{6}^{n}$ is connected. Thus, $κ (Q_{n}; C_{6}) \geq ⌈ \frac{n}{3} ⌉$ ⁠. □

Figure 4 illustrates the $C_{6}$ -structure connectivity of $Q_{4}$ ⁠. In Figure 4, the structure cut is indicated with the dotted lines.

Since $Q_{3}$ is connected and by Lemma 3.3, $κ (Q_{3}; C_{6}) \leq ⌈ \frac{3}{3} ⌉ = 1$ ⁠, $κ (Q_{3}; C_{6}) = 1 = ⌈ \frac{3}{3} ⌉$ ⁠. Also, by Lemma 3.3 and 3.6, we have the following result.

Theorem 3.7.

For $n \geq 3$ , $κ^{s} (Q_{n}; C_{6}) \leq κ (Q_{n}; C_{6}) = ⌈ \frac{n}{3} ⌉$ .

This research work is supported through the INSPIRE, India programme (IF160672) of Department of Science and Technology, Government of India for the second author. Declaration of Competing Interest: The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper. The publisher wishes to inform readers that the article “Structure and substructure connectivity of circulant graphs and hypercubes” was originally published by the previous publisher of the Arab Journal of Mathematical Sciences and the pagination of this article has been subsequently changed. There has been no change to the content of the article. This change was necessary for the journal to transition from the previous publisher to the new one. The publisher sincerely apologises for any inconvenience caused. To access and cite this article, please use Tamizh Chelvam, T., Sivagami, M., “Structure and substructure connectivity of circulant graphs and hypercubes”, Arab Journal of Mathematical Sciences, Vol. 27 No. 1, pp. 94-103. The original publication date for this paper was 24/10/2019.

References

[1]

Biggs

Algebraic Graph Theory

Cambridge University Press

1993

Google Scholar

[2]

Chatr

Zhang

Introduction To Graph Theory

Tata McGraw-Hill

2006

Google Scholar

[3]

Italo J.

Dejter

Perfect domination in regular grid graphs

Australas. J. Combin.

(

2008

)

–

114

Google Scholar

[4]

Lakshmivarahan

S.K.

Dhall

Ring, torus, hypercube architectures algorithms for parallel computing

Parallel Comput

(

1999

)

1877

–

1906

Google Scholar

Crossref

[5]

Lee

Independent perfect domination sets in Cayley graphs

J. Graph Theory

(

) (

2001

)

213

–

219

Google Scholar

Crossref

[6]

Cheng-Kuan

Lin

Lili

Zhang

Jianxi

Fan

Dajin

Wang

Structure connectivity and substructure connectivity of hypercubes

Theoret. Comput. Sci.

634

(

2016

)

–

107

https://doi.org/10.1016/j.tcs.2016.04.014

Google Scholar

Crossref

[7]

S.A.

Mane

Structure connectivity of hypercubes

AKCE Int. J. Graphs Comb.

(

) (

2018

)

–

Google Scholar

Crossref

[8]

Tamizh Chelvam

Rani

Independent domination number of Cayley graphs on

ℤ_{n}

J. Combin. Math. Combin. Comput.

(

2009

)

251

–

255

Google Scholar

[9]

Tamizh Chelvam

Sivagami

Domination in Cayley graphs: A survey

AKCE Int. J. Graphs Comb.

(

2019

)

–

https://doi.org/10.1016/j.akcej.2017.11.005

Google Scholar

Crossref

[10]

J.F.

Wang

An investigation of the network reliability properties of circulant graphs (Doctoral dissertation)

Stevens Institute of Technology

1983

Google Scholar

2019

T. Tamizh Chelvam and M. Sivagami

Published in the Arab Journal of Mathematical Sciences. Published by Emerald Publishing Limited. This article is published under the Creative Commons Attribution (CC BY 4.0) license. Anyone may reproduce, distribute, translate and create derivative works of this article (for both commercial and non-commercial purposes), subject to full attribution to the original publication and authors. The full terms of this license may be seen at http://creativecommons.org/licences/by/4.0/legalcode

Structure and substructure connectivity of circulant graphs and hypercubes

1. Introduction

2. Structure and substructure connectivity of circulant graphs

3. Structure and substructure connectivity of hypercubes

References

Data & Figures

Contents

Supplements

References

New and popular articles

Email Alerts

Cited By

Languages

Structure and substructure connectivity of circulant graphs and hypercubes

1. Introduction

2. Structure and substructure connectivity of circulant graphs

3. Structure and substructure connectivity of hypercubes

References

Data & Figures

Contents

Supplements

References

Related

New and popular articles

Email Alerts

Suggested Reading

Recommended for you

Cited By

Languages

Sharing Unavailable