Advertisement
Published in:
16-08-2018
A polynomial algorithm determining cyclic vertex connectivity of k-regular graphs with fixed k
Published in: Journal of Combinatorial Optimization | Issue 3/2019
Log inActivate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
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 \(c \kappa (G)\) and its time complexity is bounded by \(O(v^{15/2})\).