Cyclic Vertex Connectivity of Star Graphs

被引：0

作者：

Yu, Zhihua ^{[1
]}

Liu, Qinghai ^{[1
]}

Zhang, Zhao ^{[1
]}

机构：

[1] Xinjiang Univ Urumqi, Coll Math & Syst Sci, Xinjiang 830046, Peoples R China

来源：

COMBINATORIAL OPTIMIZATION AND APPLICATIONS, PT 1 | 2010年 / 6508卷

关键词：

star graph; cyclic vertex-connectivity; CONDITIONAL CONNECTIVITY; INTERCONNECTION NETWORKS;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

For a connected graph G, a vertex subset F subset of V (G) is a cyclic vertex-cut of G if G - F is disconnected and at least two of its components contain cycles. The cardinality of a minimum cyclic vertex-cut of G, denoted by kappa(c)(G), is the cyclic vertex-connectivity of G. In this paper, we show that for any integer n >= 4, the n-dimensional star graph SG(n) has kappa(c)(SG(n)) = 6(n - 3).

引用

页码：212 / 221

页数：10

共 50 条

[31] A polynomial algorithm determining cyclic vertex connectivity of k-regular graphs with fixed k
Jun Liang
Dingjun Lou
Journal of Combinatorial Optimization, 2019, 37 : 1000 - 1010
[32] CYCLIC CONNECTIVITY OF STAR GRAPH
Liu, Qinghai
Zhang, Zhao
Yu, Zhihua
DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2011, 3 (04) : 433 - 442
[33] Efficient algorithm for the vertex connectivity of trapezoid graphs
Ilic, Aleksandar
INFORMATION PROCESSING LETTERS, 2013, 113 (10-11) : 398 - 404
[34] 2-Vertex Connectivity in Directed Graphs
Georgiadis, Loukas
Italiano, Giuseppe F.
Laura, Luigi
Parotsidis, Nikos
AUTOMATA, LANGUAGES, AND PROGRAMMING, PT I, 2015, 9134 : 605 - 616
[35] Using expander graphs to find vertex connectivity
Gabow, HN
41ST ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 2000, : 410 - 420
[36] Connectivity Oracles for Graphs Subject to Vertex Failures
Duan, Ran
Pettie, Seth
PROCEEDINGS OF THE TWENTY-EIGHTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2017, : 490 - 509
[37] Using expander graphs to find vertex connectivity
Gabow, Harold N.
JOURNAL OF THE ACM, 2006, 53 (05) : 800 - 844
[38] Algebraic Connectivity and Disjoint Vertex Subsets of Graphs
Sun, Yan
Li, Faxu
MATHEMATICAL PROBLEMS IN ENGINEERING, 2020, 2020
[39] PARTITION CONDITIONS AND VERTEX-CONNECTIVITY OF GRAPHS
GYORI, E
COMBINATORICA, 1981, 1 (03) : 263 - 273
[40] 2-vertex connectivity in directed graphs
Georgiadis, Loukas
Italiano, Giuseppe F.
Laura, Luigi
Parotsidis, Nikos
INFORMATION AND COMPUTATION, 2018, 261 : 248 - 264

← 1 2 3 4 5 →