# On Cyclic-Vertex Connectivity ofn,k-Star Graphs

Authors: Yalan Li; Shumin Zhang; Chengfu Ye
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

A vertex subsetF⊆VG is a cyclic vertex-cut of a connected graph G if G−F is disconnected and at least two of its components contain cycles. The cyclic vertex-connectivity κcG is denoted as the cardinality of a minimum cyclic vertex-cut. In this paper, we show that the cyclic vertex-connectivity of the n,k-star network Sn,k is κcSn,k=n+2k−5 for any integer n≥4 and k≥2.


---

## Body

## 1. Introduction

LetG=V,E be a simple connected graph, where V and E are the vertex set and the edge set, respectively. GH is an induced subgraph by H⊆V, whose vertex set is H and whose edge set consists of all the edges of G with both ends in H. For any vertex v, define the neighborhood NGv=u∈V|u,v∈E. Let S⊆VG and the set ∪v∈SNGv∖S is denoted by NGS. We use Nv to replace NGv, NS to replace NGS, and NS to replace NGS. A graph G is said to be k-regular if dv=k for any vertex v∈V. For any subset F⊆VG, G∖F or G−F denotes the graph obtained by removing all vertices in F from G. If there exists a nonempty subset F⊆G such that G∖F is disconnected, then F is called a vertex-cut of G. The connectivity κG is the minimum number of vertices whose removal results in a disconnected graph or only one vertex left. Let δG and gG denote the minimum degree and the girth of G, respectively. As usual, we use Kn and Cn to denote the complete graph and the cycle of order n, respectively.In this work, we study a kind of restricted vertex-connectivity known as the cyclic vertex-connectivity. A vertex subsetF⊂V is a cyclic vertex-cut of G if G−F has at least two components containing cycles. Not all connected graphs have a cyclic vertex-cut. The cyclic vertex-connectivity κcG of a graph G is the cardinality of the minimum cyclic vertex-cut of G. When G has no cyclic vertex-cut, the definition of κcG can be found in [1] using Betti number. A graph G is said to be κc-connected if G has a cyclic vertex-cut. Similarly, changing “edge” to “vertex,” the cyclic edge-connectivity λcG of graph G can be defined.The definition of the cyclic vertex- (edge-) connectivity dates to Tait in attacking four color conjecture [2] and the graph colouring [2, 3]. It is used in many classic fields, such as integer flow conjectures [4] and n-extendable graphs [5, 6]. In many works, the cyclic vertex-connectivity has been studied. Cheng et al. [7] studied the cyclic vertex-connectivity of Cayley graphs generated by transposition trees. Yu et al. [8] obtained the cyclic vertex-connectivity of star graphs. For more research studies on the cyclic vertex-connectivity, see [7, 9–11] for references.This paper focuses on the cyclic vertex-connectivity of then,k-star network Sn,k. We will show that κcSn,k=n+2k−5 for any integer n≥4,k≥2 and find out the minimum circle vertex-cut structure of the n,k-star network Sn,k.


## 2. Some Preliminaries

We provide the definition of then,k-star graph Sn,k and its structural properties, which are useful for the following discussion.For convenience, letn=1,2,…,n and Vn,k=q1q2⋯qk:qi∈n,qi≠qj,1≤i≠j≤k for any integers n and k with 1≤k≤n. Clearly, Vn,k=n!/n,k!.Definition 1 (see [12]).
Then,k-star graph, denoted by Sn,k (see Figure 1), is a graph with the vertex-set Vn,k and the edge set defined as follows:(1)
A vertexq1q2⋯qi⋯qk is adjacent to the vertex qiq2⋯q1⋯qk through an edge of dimension i, where 2≤i≤k (i.e., exchange q1 with qi)(2)
A vertexq1q2⋯qi⋯qk is adjacent to the vertex yq2⋯qi⋯qk through an edge of dimension 1, where y∈n∖q1,q2,…,qk (i.e., replace q1 by y)Figure 1
Some examples of the(n, k)-star graph S3,1, S4,1, S4,2, and S5,2The edges of type (1) are referred to asi-edges, and the corresponding neighboring vertices are called i-neighbors. The edges of type (2) are referred to as 1-edges, and the corresponding neighboring vertices are called 1-neighbors. Let Sn,ki be induced by all the vertices having the symbol i in one of the rightmost k−1 positions of Sn,k. Clearly, Sn,k can be decomposed into n subgraphs Sn,ki and Sn,ki≅Sn−1,k−1, where 1≤i≤n and 2≤k≤n.Lemma 1 (see [13]).
Then,k-star graph Sn,k has the following properties:(1)
Sn,k is a graph of degree n−1 with n!/n−k! vertices and n−1n!/2n−k! edges.(2)
Sn,1≅Kn, Sn,n−1≅Sn, and Sn,n−2≅ANn, where Kn is a complete graph, Sn is a n-dimensional star graph, and ANn is a n-dimensional alternating group network.(3)
Ei,j is the set of all cross edges between any two subgraphs Sn,ki and Sn,kji≠j∈n, and Ei,j=n−2!/n−k!.(4)
For any two verticesu and v in Sn,k,(1)Nu∩Nv=n−k−1,ifu,v∈ESn,kis1−edge,1,ifu,v∉ESn,kandNu∩Nv≠∅,0,otherwise.Lemma 2 (see [13]).
Sn,k is a n−1-regular n−1-connected graph.Theorem 1 (see [14]).
LetF be a faulty vertex set of Sn,kn≥5,k≥3,n−k≥2 with F≤n+2k−6. Then, the survival graph Sn,k\F satisfies one of the following conditions:(1)
Sn,k\F is connected(2)
Sn,k\F has two components, one of which has exactly one vertex or two vertices with one 1-edge(3)
Sn,k\F has three components, two of which are singletonsLemma 3 (see [13]).
If a cycle has a length at least 6 in anSn,k, then it contains one i-edge, 2≤i≤k.Theorem 2 (see [8]).
For any integern≥4, κcSn=6n−3.


## 3. Main Result

By Lemma1 and Theorem 2, we know Sn,n−1≅Sn if k=n−1 and κcSn=6n−3. Thus, we determine the value of κcSn,k with n−k≥2 for n≥4,k≥2.Lemma 4.
Forn≥4, the girth of Sn,2 is 3 and the edges of every 3-cycle are 1-edges.Proof.
Choose any vertexu1 from Sn,2 and make it as u1=q1q2. Since n≥4, there exist qi,qj∈n\q1,q2 and qi≠qj. From the definition of Sn,2, we have two vertices u2=qiq2 and u3=qjq2 in VSn,2 and u1u2,u2u3,u3u1∈ESn,2. Clearly, u1u2u3u1 is one 3-cycle, and all the edges of it are 1-edges. Hence, the lemma holds.Lemma 5.
LetC be any cycle of length 3 in Sn,2n≥4. Then, NSn,2C=n−1.Proof.
From Lemma4, we can suppose C=q1q2q3q2q4q2q1q2. Let S=q5q2,q6q2,…,qnq2⊆VSn,2, then S=n−4. By the definition of Sn,2, we have(2)NSn,2q1q2\q3q2,q4q2=S∪q2q1,NSn,2q3q2\q1q2,q4q2=S∪q2q3,NSn,2q4q2\q1q2,q3q2=S∪q2q4.
So,(3)NSn,2C=S∪q2q1,q2q3,q2q4=n−4+3=n−1.Lemma 6.
LetC be a 3-cycle of Sn,2n≥4. Then, NSn,2C is a cyclic vertex-cut of Sn,2.Proof.
Clearly,Sn,2−NSn,2C is disconnected and contains C as a connected component. In order to prove the lemma, it suffices to show that the subgraph H=Sn,2−NSn,2C has a cycle. In fact, we can prove a stronger property δH≥2 as follows.
SupposeC=q1q2q3q2q4q2q1q2. By Lemma 5, NSn,2C=S∪q2q1,q2q3,q2q4 and S=q5q2,q6q2,…,qnq2. If δH≤1, and then there exists a vertex v∈VH satisfying NHv=1 and v∉S∪q2q1,q2q3,q2q4. Since Sn,2 is n−1-regular, v∈VH has at least n−2≥2 neighbors in NSn,2C. Let v1andv2 be two distinct vertices in NSn,2v∩NSn,2C⊆S∪q2q1,q2q3,q2q4.
Ifv1,v2∈S, without loss of generality, let v1=qiq2, v2=qjq2, where qi,qj∈q5,q6,…,qn and qi≠qj. By Definition 1, all the edges in Sn,2 are i-edges or 1-edges. Since vv1,vv2∈ESn,2, v=qsq2, and qs∈q5,q6,…,qn∖qi,qj. It means v∈S, contradicting v∉S∪q2q1,q2q3,q2q4.
Ifv1∈S and v2∈q2q1,q2q3,q2q4, without loss of generality, then let v1=qiq2 and v2=q2qj, where qi∈q5,q6,…,qn and qj∈q1,q3,q4. Since vv1,vv2∈ESn,2, v=qjq2, and qj∈q1,q3,q4, it means v∈C, contradicting v∈H=Sn,2−NSn,2C.
Ifv1,v2∈q2q1,q2q3,q2q4, clearly, if vv1∈ESn,2, then vv2∉ESn,2. If vv2∈ESn,2, then vv1∉ESn,2, similarly, contradicting vv1,vv2∈ESn,2.
From the above discussion, we know thatδH≥2. Furthermore, NSn,2C is a cyclic vertex-cut of Sn,2.
Combining Lemma5 and 6, we have the following theorem.Theorem 3.
For any integern≥4, κcSn,2=n−1.Proof.
LetC be a 3-cycle in Sn,2 and F=NSn,2C. By Lemmas 5 and 6, F is a cyclic vertex-cut of Sn,2. Hence, κcSn,2≤F=n−1. By Lemma 2, κSn,2=n−1. We have κcSn,2≥κSn,2=n−1, and then κcSn,2=n−1.Theorem 4.
For any integern≥5,k≥3,n−k≥2, and κcSn,k=n+2k−5.Proof.
LetF be a faulty vertex set of Sn,k with F≤n+2k−6. By Theorem 1, Sn,k−F is connected or Sn,k−F is disconnected, and at most one of its component contains cycles. Hence, κcSn,k≥n+2k−5. To prove the converse, we need to find a cyclic vertex-cut F of Sn,k with F=n+2k−5.
Supposev=q1q2⋯qk∈VSn,k, we have two vertices u, w such that vu and vw are 1-edges by n−k≥2. Without loss of generality, we can assume u=qk+1q2⋯qk and w=qk+2q2⋯qk. From the definition of Sn,k, we have uw∈ESn,k. Hence, C3=uvwu in Sn,k. Let A=qjq2⋯qk|j=k+3,k+4,…,n, then A=NSn,ku∩NSn,kv∩NSn,kw and A=n−k−2. Since u,v,w have another k−1i-neighbors in Sn,k∖A, respectively, NSn,kC3=A+3k−1=n−k−2+3k−1=n+2k−5. Clearly, Sn,k−NSn,kC3 is disconnected and contains C3 as a connected component. In order to find a cyclic vertex-cut, it suffices to show that Sn,k−NSn,kC3 has a cycle. In fact, we can prove δSn,k−NSn,2C3≥2. Suppose that there exists one vertex x of Sn,k−NSn,kC3 with dSn,k−NSn,kC3x=1. Since Sn,k is n−1-regular n−1≥4, NSn,kx∩NSn,kC3≥3.
Ifx is adjacent to one neighbor vertex of u, v, and w, respectively, it means there are three vertices u′, v′, and w′ such that u′∈NSn,k−C3u, v′∈NSn,k−C3v, w′∈NSn,k−C3w, and u′,v′,w′⊆NSn,kx∩NSn,kC3. Then, all of uu′,vv′,andww′ are i-edges. Let u′=qsq2⋯qk+1⋯qk, v′=qtq2⋯q1⋯qk, w′=qmq2⋯qk+2⋯qk and s,t,m∈2,3,…,k. By the definition of Sn,k, we know x is adjacent to at most one of u′, v′, and w′, a contradiction.
Ifx is adjacent to two neighbor vertices of u and one neighbor vertex of v, it means there are three vertices u1, u2, and v1 such that u1,u2∈NSn,k−C3u, v1∈NSn,k−C3v, and u1,u2,v1⊆NSn,kx∩NSn,kC3. From the definition of Sn,k, both uu1anduu2 are 1-edges and x=qtq2⋯qk+1⋯qk, t∈k+3,k+4,…,n. Furthermore, x∈NC3, a contradiction with x∈Sn,k−NSn,kC3.
Ifx is adjacent to three neighbor vertices of u, it means there are three vertices u1, u2, and u3 such that u1,u2,u3∈NSn,k−C3u and u1,u2,u3⊆NSn,kx∩NSn,kC3. From the definition of Sn,k, all of uu1,uu2,anduu3 are 1-edges and x=qtq2⋯qk+1⋯qk and t∈k+3,k+4,…,n. Furthermore, x∈NC3, a contradiction with x∈Sn,k−NSn,kC3.
From the above discussion, we know thatδSn,k−NSn,2C3≥2. Then, Sn,k−NSn,kC3 contains a cycle, and NSn,kC3 is a cyclic vertex-cut of Sn,k with NSn,kC3=n+2k−5. Hence, κcSn,k≥n+2k−5. The theorem holds.
Combining Theorems3 and 4, we have the following theorem.Theorem 5.
For any integern≥4,k≥2,andκcSn,k=n+2k−5.


## 4. Conclusion

In this paper, we determine the cyclic vertex-connectivity of then,k-star network Sn,k. We can consider the cyclic vertex-connectivity of other graphs and the cyclic edge-connectivity of the n,k-star network Sn,k in our future research.



---

*Source: 5570761-2021-04-13.xml*