A polynomial algorithm determining cyclic vertex connectivity of 4-regular graphs

Jun Liang, Dingjun Lou (), Zongrong Qin and Qinglin Yu
Additional contact information
Jun Liang: South China Normal University
Dingjun Lou: Sun Yat-sen University
Zongrong Qin: Sun Yat-sen University
Qinglin Yu: Thompson Rivers University

Journal of Combinatorial Optimization, 2019, vol. 38, issue 2, No 14, 589-607

Abstract: Abstract For a connected graph G, a set S of vertices is a cyclic vertex cutset if $$G - S$$ G - S is not connected and at least two components of $$G-S$$ G - S contain a cycle respectively. The cyclic vertex connectivity $$c \kappa (G)$$ c κ ( G ) is the cardinality of a minimum cyclic vertex cutset. In this paper, for a 4-regular graph G with v vertices, we give a polynomial time algorithm to determine $$c \kappa (G)$$ c κ ( G ) of complexity $$O(v^{15/2})$$ O ( v 15 / 2 ) .

Keywords: Cyclic vertex connectivity; 4-Regular graph; Maximum flow; Time complexity (search for similar items in EconPapers)
Date: 2019
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-019-00400-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:38:y:2019:i:2:d:10.1007_s10878-019-00400-6

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-019-00400-6

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().