A polynomial algorithm determining cyclic vertex connectivity of k-regular graphs with fixed k

被引：9

作者：

Liang, Jun ^{[1
,2
]}

Lou, Dingjun ^{[2
]}

机构：

[1] South China Normal Univ, Network Ctr, Guangzhou 510631, Guangdong, Peoples R China

[2] Sun Yat Sen Univ, Sch Data & Comp Sci, Guangzhou 510006, Guangdong, Peoples R China

来源：

JOURNAL OF COMBINATORIAL OPTIMIZATION | 2019年 / 37卷 / 03期

关键词：

Cyclic vertex connectivity; k-Regular graph; Maximum flow; Time complexity; EDGE-CONNECTIVITY;

D O I：

10.1007/s10878-018-0332-4

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

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 of G - S contain a cycle respectively. The cyclic vertex connectivity C kappa (G) is the cardinality of a minimum cyclic vertex cutset. In this paper, for a k-regular graph G with fixed k value, we give a polynomial time algorithm to determine oc(G) and its time complexity is bounded by O (v(15/2)).

引用

页码：1000 / 1010

页数：11

共 50 条

[1] 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
[2] A polynomial algorithm determining cyclic vertex connectivity of 4-regular graphs
Jun Liang
Dingjun Lou
Zongrong Qin
Qinglin Yu
Journal of Combinatorial Optimization, 2019, 38 : 589 - 607
[3] A polynomial algorithm determining cyclic vertex connectivity of 4-regular graphs
Liang, Jun
Lou, Dingjun
Qin, Zongrong
Yu, Qinglin
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2019, 38 (02) : 589 - 607
[4] On k-regular edge connectivity of chemical graphs
Ediz, Suleyman
Ciftci, Idris
MAIN GROUP METAL CHEMISTRY, 2022, 45 (01) : 106 - 110
[5] The connected vertex cover problem in k-regular graphs
Li, Yuchao
Wang, Wei
Yang, Zishen
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2019, 38 (02) : 635 - 645
[6] Vertex partitions by connected monochromatic k-regular graphs
Sárközy, GN
Selkow, SM
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2000, 78 (01) : 115 - 122
[7] The connected vertex cover problem in k-regular graphs
Yuchao Li
Wei Wang
Zishen Yang
Journal of Combinatorial Optimization, 2019, 38 : 635 - 645
[8] EMBEDDING K-REGULAR GRAPHS IN K+1-REGULAR GRAPHS
GARDINER, A
JOURNAL OF THE LONDON MATHEMATICAL SOCIETY-SECOND SERIES, 1983, 28 (DEC): : 393 - 400
[9] An Improved Bound for Vertex Partitions by Connected Monochromatic K-Regular Graphs
Sarkoezy, Gabor N.
Selkow, Stanley M.
Song, Fei
JOURNAL OF GRAPH THEORY, 2013, 73 (02) : 127 - 145
[10] A polynomial time algorithm for cyclic vertex connectivity of cubic graphs
Liang, Jun
Lou, Dingjun
Zhang, Zanbo
INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2017, 94 (07) : 1501 - 1514

← 1 2 3 4 5 →