A new lower bound for the eternal vertex cover number of graphs

Jasine Babu () and Veena Prabhakaran ()
Additional contact information
Jasine Babu: Indian Institute of Technology Palakkad
Veena Prabhakaran: Indian Institute of Technology Palakkad

Journal of Combinatorial Optimization, 2022, vol. 44, issue 4, No 18, 2482-2498

Abstract: Abstract 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 $$\epsilon >0$$ ϵ > 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-\epsilon $$ 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.

Keywords: Eternal vertex cover; Lower bound; Chordal graphs; Internally triangulated planar graphs (search for similar items in EconPapers)
Date: 2022
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-021-00764-8 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:44:y:2022:i:4:d:10.1007_s10878-021-00764-8

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

DOI: 10.1007/s10878-021-00764-8

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 ().