Let G � (V, E) be a simple connected graph, where V and E are the vertex set and the edge set, respectively. G[H] is an induced subgraph by H⊆V,… Click to show full abstract
Let G � (V, E) be a simple connected graph, where V and E are the vertex set and the edge set, respectively. G[H] 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 NG(v) � u ∈ V| { (u, v) ∈ E}. Let S⊆V(G) and the set ∪ v∈SNG(v)∖S is denoted by NG(S). We use N(v) to replace NG(v), N(S) to replace NG(S), and N[S] to replace NG[S]. A graph G is said to be k-regular if d(v) � k for any vertex v ∈ V. For any subset F⊆V(G), 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. +e connectivity κ(G) is the minimum number of vertices whose removal results in a disconnected graph or only one vertex left. Let δ(G) and g(G) 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 subset F ⊂ 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.+e cyclic vertex-connectivity κc(G) of a graph G is the cardinality of the minimum cyclic vertexcut of G. When G has no cyclic vertex-cut, the definition of κc(G) 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 λc(G) of graph G can be defined. +e 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 vertexconnectivity 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. +is paper focuses on the cyclic vertex-connectivity of the (n, k)-star network Sn,k. We will show that κc(Sn,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.
               
Click one of the above tabs to view related content.