Header menu link for other important links
A new lower bound for the eternal vertex cover number of graphs
, V. Prabhakaran
Published in Springer
Pages: 1 - 17
The main result in this paper is a new lower bound to the eternal vertex cover number (evc number) of an arbitrary graph G in terms of the size of the smallest vertex cover in G that includes all the cut vertices of G. As a consequence, we obtain a quadratic complexity algorithm for finding the evc number of any chordal graph. Another consequence is a polynomial time approximation scheme for finding the evc number of internally triangulated planar graphs, for which exact determination of evc number is known to be NP-hard (Babu et al. in Discrete Appl Math, 2021. https://doi.org/10.1016/j.dam.2021.02.004). The lower bound is proven by considering a decomposition of the graph into a collection of edge disjoint induced subgraphs, and deriving a lower bound for the evc number of the whole graph in terms of bounds obtained for the subgraphs. As another consequence of the bounding technique, we obtain a construction of a family of biconnected bipartite graphs such that for any ϵ> 0 , there exists a graph in the family such that the ratio of its evc number to the size of its minimum vertex cover exceeds 2 - ϵ. This construction is asymptotically optimal, as it is known (Klostermeyer and Mynhardt in Aust J Comb 45:235–250, 2009) that this ratio has to be strictly less than 2 for biconnected graphs. © 2021, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.
About the journal
JournalData powered by TypesetJournal of Combinatorial Optimization
PublisherData powered by TypesetSpringer
Open AccessNo