License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2023.68
URN: urn:nbn:de:0030-drops-186025
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18602/
Go to the corresponding LIPIcs Volume Portal

Misra, Neeldhara ; Nanoti, Saraswati Girish

Spartan Bipartite Graphs Are Essentially Elementary

pdf-format:
LIPIcs-MFCS-2023-68.pdf (0.7 MB)

Abstract

We study a two-player game on a graph between an attacker and a defender. To begin with, the defender places guards on a subset of vertices. In each move, the attacker attacks an edge. The defender must move at least one guard across the attacked edge to defend the attack. The defender wins if and only if the defender can defend an infinite sequence of attacks. The smallest number of guards with which the defender has a winning strategy is called the eternal vertex cover number of a graph G and is denoted by evc(G). It is clear that evc(G) is at least mvc(G), the size of a minimum vertex cover of G. We say that G is Spartan if evc(G) = mvc(G). The characterization of Spartan graphs has been largely open. In the setting of bipartite graphs on 2n vertices where every edge belongs to a perfect matching, an easy strategy is to have n guards that always move along perfect matchings in response to attacks. We show that these are essentially the only Spartan bipartite graphs.

BibTeX - Entry

@InProceedings{misra_et_al:LIPIcs.MFCS.2023.68,
  author =	{Misra, Neeldhara and Nanoti, Saraswati Girish},
  title =	{{Spartan Bipartite Graphs Are Essentially Elementary}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{68:1--68:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18602},
  URN =		{urn:nbn:de:0030-drops-186025},
  doi =		{10.4230/LIPIcs.MFCS.2023.68},
  annote =	{Keywords: Bipartite Graphs, Eternal Vertex Cover, Perfect Matchings, Elementary, Spartan}
}

Keywords: Bipartite Graphs, Eternal Vertex Cover, Perfect Matchings, Elementary, Spartan
Collection: 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Issue Date: 2023
Date of publication: 21.08.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI