Super Rk-vertex-connectedness

摘要

For a graph G=(V,E), a subset F ⊆ V(G) is called an Rk-vertex-cut of G if G−F is disconnected and each vertex u∈V(G)−F has at least k neighbours in G−F. The Rk-vertex-connectivity of G, denoted by κk(G), is the cardinality of a minimum Rk-vertex-cut of G. In this paper, we further study the Rk-vertex-connectivity by introducing the concept, called super Rk-vertex-connectedness. The graph G is called super Rk-vertex-connectedness if, for every minimum Rk-vertex-cut S, G−S contains a component which is isomorphic to a certain graph H, where H is related to the graph G and integer k. For the Cayley graphs generated by wheel graphs, H is isomorphic to K2 when k=1 and H is isomorphic to C4 when k=2. In this paper, we show that the Cayley graphs generated by wheel graphs are super R1-vertex-connectedness and super R2-vertex-connectedness. Our studies generalize the main result in [8].