Part of the book series:Lecture Notes in Computer Science ((LNTCS,volume 12273))
Included in the following conference series:
818Accesses
Abstract
We obtain a new lower bound for the eternal vertex cover number of an arbitrary graphG, in terms of the cardinality of a vertex cover of minimum size inG containing all its cut vertices. The consequences of the lower bound include a quadratic time algorithm for computing the eternal vertex cover number of chordal graphs.
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 11439
- Price includes VAT (Japan)
- Softcover Book
- JPY 14299
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The results in Fomin et al. [6] are given for the variant of the problem in which more than one guard is allowed to be on a vertex in a configuration. But, the proof can be easily modified for to work for the other model as well.
- 2.
Note that the definition of this graph class is more general than the one in[2].
References
Anderson, M., Brigham, R., Carrington, J., Dutton, R., Vitray, R., Yellen, J.: Graphs simultaneously achieving three vertex cover numbers. J. Comb. Math. Comb. Comput.91, 275–290 (2014)
Babu, J., Chandran, L.S., Francis, M., Prabhakaran, V., Rajendraprasad, D., Warrier, J.N.: On graphs whose eternal vertex cover number and vertex cover number coincide. arxiv,https://arxiv.org/abs/1812.05125v2 (April 2019)
Babu, J., Chandran, L.S., Francis, M., Prabhakaran, V., Rajendraprasad, D., Warrier, J.N.: On graphs with minimal eternal vertex cover number. In: Pal, S.P., Vijayakumar, A. (eds.) CALDAM 2019. LNCS, vol. 11394, pp. 263–273. Springer, Cham (2019).https://doi.org/10.1007/978-3-030-11509-8_22
Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. J. ACM41(1), 153–180 (1994)
Chartrand, G., Pippert, R.E.: Locally connected graphs. Časopis pro pěstování matematiky99(2), 158–163 (1974)
Fomin, F.V., Gaspers, S., Golovach, P.A., Kratsch, D., Saurabh, S.: Parameterized algorithm for eternal vertex cover. Inf. Process. Lett.110(16), 702–706 (2010)
Goddard, W., Hedetniemi, S.M., Hedetniemi, S.T.: Eternal security in graphs. J. Combin. Math. Combin. Comput.52, 169–180 (2005)
Goldwasser, J.L., Klostermeyer, W.F.: Tight bounds for eternal dominating sets in graphs. Discrete Math.308(12), 2589–2593 (2008)
Hartnell, B., Mynhardt, C.: Independent protection in graphs. Discrete Math.335, 100–109 (2014)
Klostermeyer, W.F., Mynhardt, C.M.: Graphs with equal eternal vertex cover and eternal domination numbers. Discrete Math.311, 1371–1379 (2011)
Klostermeyer, W., Mynhardt, C.: Edge protection in graphs. Austr. J. Comb.45, 235–250 (2009)
Klostermeyer, W.F., Mynhardt, C.: Vertex covers and eternal dominating sets. Discrete Appl. Math.160(7), 1183–1190 (2012)
Rinemberg, M., Soulignac, F.J.: The eternal dominating set problem for interval graphs. Inf. Process. Lett.146, 27–29 (2019)
Rose, D.J., Tarjan, R.E., Lueker, G.S.: Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput.5(2), 266–283 (1976)
Author information
Authors and Affiliations
Indian Institute of Technology Palakkad, Palakkad, India
Jasine Babu & Veena Prabhakaran
- Jasine Babu
You can also search for this author inPubMed Google Scholar
- Veena Prabhakaran
You can also search for this author inPubMed Google Scholar
Corresponding author
Correspondence toJasine Babu.
Editor information
Editors and Affiliations
Georgia State University, Atlanta, USA
Donghyun Kim
Department of Mathematics and Physics, North Carolina Central University, Durham, NC, USA
R. N. Uma
Computer Science, Georgia State University, Atlanta, GA, USA
Zhipeng Cai
Korea University, Seoul, Korea (Republic of)
Dong Hoon Lee
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Babu, J., Prabhakaran, V. (2020). A New Lower Bound for the Eternal Vertex Cover Number of Graphs. In: Kim, D., Uma, R., Cai, Z., Lee, D. (eds) Computing and Combinatorics. COCOON 2020. Lecture Notes in Computer Science(), vol 12273. Springer, Cham. https://doi.org/10.1007/978-3-030-58150-3_3
Download citation
Published:
Publisher Name:Springer, Cham
Print ISBN:978-3-030-58149-7
Online ISBN:978-3-030-58150-3
eBook Packages:Computer ScienceComputer Science (R0)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative