For a connected graph G, a set S of vertices is a cyclic vertex cutset if G−S is not connected and at least two components contain a cycle respectively. The cyclic vertex connectivity is the cardinality of a minimum cyclic vertex cutset. In this paper, for any k-regular graph G with girth g and the number of vertices, we give a sufficient condition for the cyclic vertex connectivity . Then we give a polynomial time algorithm to determine for a cubic graph G. The time complexity of the algorithm is bounded by .
1 December 2020 in Journal of Physics: Conference Series
At present, there are few studies about the link failure and reliability of software defined satellite network (SDSN). However, the inter-satellite links (ISLs) may break down because of the long distance between the satellites, the high relative moving speed and the easy interference of the wireless channel. At the same time, most researches on controller deployment in SDSN only consider the transmission delay but ignore the processing delay. To solve these problems, considering the failure probability of intersatellite link, the failure probability model of ISLs is designed, the queuing delay and processing delay are added into the delay model, and the software defined satellite network reliability analysis model based on control delay is established. This model can describe the reliability of the network against link failure. The simulation results show that the model is consistent with the actual situation and can provide some reference value for controller deployment in SDSN.