A note on the eternal dominating set problem

We consider the “all guards move” model for the eternal dominating set problem. A set of guards form a dominating set on a graph and at the beginning of each round, a vertex not in the dominating set is attacked. To defend against the attack, the guards move (each guard either passes or moves to a n...

Full description

Saved in:
Bibliographic Details
Published in:International journal of game theory 2018-05, Vol.47 (2), p.543-555
Main Authors: Finbow, Stephen, Gaspers, Serge, Messinger, Margaret-Ellen, Ottaway, Paul
Format: Article
Language:English
Subjects:
Algorithms
Behavioral/Experimental Economics
Cameras
Combinatorial analysis
Dominance
Economic Theory/Quantitative Economics/Mathematical Methods
Economics
Economics and Finance
Game Theory
Games
Guards
Operations Research/Decision Theory
Original Paper
Social and Behav. Sciences
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c381t-4f27504807fa69228b39680e3b697086152d5ebd7369d2105dcc56b73e7c37a73
cites cdi_FETCH-LOGICAL-c381t-4f27504807fa69228b39680e3b697086152d5ebd7369d2105dcc56b73e7c37a73
container_end_page 555
container_issue 2
container_start_page 543
container_title International journal of game theory
container_volume 47
creator Finbow, Stephen
Gaspers, Serge
Messinger, Margaret-Ellen
Ottaway, Paul
description We consider the “all guards move” model for the eternal dominating set problem. A set of guards form a dominating set on a graph and at the beginning of each round, a vertex not in the dominating set is attacked. To defend against the attack, the guards move (each guard either passes or moves to a neighboring vertex) to form a dominating set that includes the attacked vertex. The minimum number of guards required to defend against any sequence of attacks is the “eternal domination number” of the graph. In 2005, it was conjectured [Goddard et al. (J. Combin. Math. Combin. Comput. 52:169–180, 2005)] there would be no advantage to allow multiple guards to occupy the same vertex during a round. We show this is, in fact, false. We also describe algorithms to determine the eternal domination number for both models for eternal domination and examine the related combinatorial game, which makes use of the reduced canonical form of games.
doi_str_mv 10.1007/s00182-018-0623-0
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_2035475454</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2035475454</sourcerecordid><originalsourceid>FETCH-LOGICAL-c381t-4f27504807fa69228b39680e3b697086152d5ebd7369d2105dcc56b73e7c37a73</originalsourceid><addsrcrecordid>eNp1kM1OwzAQhC0EEqHwANwsccWwXsd2cqwqKEiVuMDZys-mpGqTYrsH3h5HQeLEZfYy38xqGLuV8CAB7GMAkAWKJAIMKgFnLJO5QiHRwjnLABCERWsu2VUIO0gMFJix-yUfxkh8HHj8JE6R_FDteTse-qGK_bDlgSI_-rHe0-GaXXTVPtDN712wj-en99WL2LytX1fLjWhUIaPIO7Qa8gJsV5kSsahVaQogVZsytRqpsdVUt1aZskUJum0abWqryDbKVlYt2N2cm3q_ThSi242n6a_gEJTOrc51nlxydjV-DMFT546-P1T-20lw0yhuHsUlcdMoDhKDMxOSd9iS_0v-H_oBe8dhMQ</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2035475454</pqid></control><display><type>article</type><title>A note on the eternal dominating set problem</title><source>EBSCOhost Business Source Ultimate</source><source>International Bibliography of the Social Sciences (IBSS)</source><source>EBSCOhost Econlit with Full Text</source><source>ABI/INFORM Global</source><source>Springer Link</source><creator>Finbow, Stephen ; Gaspers, Serge ; Messinger, Margaret-Ellen ; Ottaway, Paul</creator><creatorcontrib>Finbow, Stephen ; Gaspers, Serge ; Messinger, Margaret-Ellen ; Ottaway, Paul</creatorcontrib><description>We consider the “all guards move” model for the eternal dominating set problem. A set of guards form a dominating set on a graph and at the beginning of each round, a vertex not in the dominating set is attacked. To defend against the attack, the guards move (each guard either passes or moves to a neighboring vertex) to form a dominating set that includes the attacked vertex. The minimum number of guards required to defend against any sequence of attacks is the “eternal domination number” of the graph. In 2005, it was conjectured [Goddard et al. (J. Combin. Math. Combin. Comput. 52:169–180, 2005)] there would be no advantage to allow multiple guards to occupy the same vertex during a round. We show this is, in fact, false. We also describe algorithms to determine the eternal domination number for both models for eternal domination and examine the related combinatorial game, which makes use of the reduced canonical form of games.</description><identifier>ISSN: 0020-7276</identifier><identifier>EISSN: 1432-1270</identifier><identifier>DOI: 10.1007/s00182-018-0623-0</identifier><language>eng</language><publisher>Berlin/Heidelberg: Springer Berlin Heidelberg</publisher><subject>Algorithms ; Behavioral/Experimental Economics ; Cameras ; Combinatorial analysis ; Dominance ; Economic Theory/Quantitative Economics/Mathematical Methods ; Economics ; Economics and Finance ; Game Theory ; Games ; Guards ; Operations Research/Decision Theory ; Original Paper ; Social and Behav. Sciences</subject><ispartof>International journal of game theory, 2018-05, Vol.47 (2), p.543-555</ispartof><rights>Springer-Verlag GmbH Germany, part of Springer Nature 2018</rights><rights>International Journal of Game Theory is a copyright of Springer, (2018). All Rights Reserved.</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c381t-4f27504807fa69228b39680e3b697086152d5ebd7369d2105dcc56b73e7c37a73</citedby><cites>FETCH-LOGICAL-c381t-4f27504807fa69228b39680e3b697086152d5ebd7369d2105dcc56b73e7c37a73</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktopdf>$$Uhttps://www.proquest.com/docview/2035475454/fulltextPDF?pq-origsite=primo$$EPDF$$P50$$Gproquest$$H</linktopdf><linktohtml>$$Uhttps://www.proquest.com/docview/2035475454?pq-origsite=primo$$EHTML$$P50$$Gproquest$$H</linktohtml><link.rule.ids>314,776,780,11668,12827,27903,27904,33202,36039,44342,74641</link.rule.ids></links><search><creatorcontrib>Finbow, Stephen</creatorcontrib><creatorcontrib>Gaspers, Serge</creatorcontrib><creatorcontrib>Messinger, Margaret-Ellen</creatorcontrib><creatorcontrib>Ottaway, Paul</creatorcontrib><title>A note on the eternal dominating set problem</title><title>International journal of game theory</title><addtitle>Int J Game Theory</addtitle><description>We consider the “all guards move” model for the eternal dominating set problem. A set of guards form a dominating set on a graph and at the beginning of each round, a vertex not in the dominating set is attacked. To defend against the attack, the guards move (each guard either passes or moves to a neighboring vertex) to form a dominating set that includes the attacked vertex. The minimum number of guards required to defend against any sequence of attacks is the “eternal domination number” of the graph. In 2005, it was conjectured [Goddard et al. (J. Combin. Math. Combin. Comput. 52:169–180, 2005)] there would be no advantage to allow multiple guards to occupy the same vertex during a round. We show this is, in fact, false. We also describe algorithms to determine the eternal domination number for both models for eternal domination and examine the related combinatorial game, which makes use of the reduced canonical form of games.</description><subject>Algorithms</subject><subject>Behavioral/Experimental Economics</subject><subject>Cameras</subject><subject>Combinatorial analysis</subject><subject>Dominance</subject><subject>Economic Theory/Quantitative Economics/Mathematical Methods</subject><subject>Economics</subject><subject>Economics and Finance</subject><subject>Game Theory</subject><subject>Games</subject><subject>Guards</subject><subject>Operations Research/Decision Theory</subject><subject>Original Paper</subject><subject>Social and Behav. Sciences</subject><issn>0020-7276</issn><issn>1432-1270</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2018</creationdate><recordtype>article</recordtype><sourceid>8BJ</sourceid><sourceid>M0C</sourceid><recordid>eNp1kM1OwzAQhC0EEqHwANwsccWwXsd2cqwqKEiVuMDZys-mpGqTYrsH3h5HQeLEZfYy38xqGLuV8CAB7GMAkAWKJAIMKgFnLJO5QiHRwjnLABCERWsu2VUIO0gMFJix-yUfxkh8HHj8JE6R_FDteTse-qGK_bDlgSI_-rHe0-GaXXTVPtDN712wj-en99WL2LytX1fLjWhUIaPIO7Qa8gJsV5kSsahVaQogVZsytRqpsdVUt1aZskUJum0abWqryDbKVlYt2N2cm3q_ThSi242n6a_gEJTOrc51nlxydjV-DMFT546-P1T-20lw0yhuHsUlcdMoDhKDMxOSd9iS_0v-H_oBe8dhMQ</recordid><startdate>20180501</startdate><enddate>20180501</enddate><creator>Finbow, Stephen</creator><creator>Gaspers, Serge</creator><creator>Messinger, Margaret-Ellen</creator><creator>Ottaway, Paul</creator><general>Springer Berlin Heidelberg</general><general>Springer Nature B.V</general><scope>AAYXX</scope><scope>CITATION</scope><scope>3V.</scope><scope>7WY</scope><scope>7WZ</scope><scope>7XB</scope><scope>87Z</scope><scope>88I</scope><scope>8AO</scope><scope>8BJ</scope><scope>8FE</scope><scope>8FG</scope><scope>8FK</scope><scope>8FL</scope><scope>8G5</scope><scope>ABJCF</scope><scope>ABUWG</scope><scope>AFKRA</scope><scope>ARAPS</scope><scope>AZQEC</scope><scope>BENPR</scope><scope>BEZIV</scope><scope>BGLVJ</scope><scope>CCPQU</scope><scope>DWQXO</scope><scope>FQK</scope><scope>FRNLG</scope><scope>F~G</scope><scope>GNUQQ</scope><scope>GUQSH</scope><scope>HCIFZ</scope><scope>JBE</scope><scope>JQ2</scope><scope>K60</scope><scope>K6~</scope><scope>K7-</scope><scope>L.-</scope><scope>L6V</scope><scope>M0C</scope><scope>M2O</scope><scope>M2P</scope><scope>M7S</scope><scope>MBDVC</scope><scope>P5Z</scope><scope>P62</scope><scope>PADUT</scope><scope>PQBIZ</scope><scope>PQBZA</scope><scope>PQEST</scope><scope>PQQKQ</scope><scope>PQUKI</scope><scope>PTHSS</scope><scope>PYYUZ</scope><scope>Q9U</scope></search><sort><creationdate>20180501</creationdate><title>A note on the eternal dominating set problem</title><author>Finbow, Stephen ; Gaspers, Serge ; Messinger, Margaret-Ellen ; Ottaway, Paul</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c381t-4f27504807fa69228b39680e3b697086152d5ebd7369d2105dcc56b73e7c37a73</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2018</creationdate><topic>Algorithms</topic><topic>Behavioral/Experimental Economics</topic><topic>Cameras</topic><topic>Combinatorial analysis</topic><topic>Dominance</topic><topic>Economic Theory/Quantitative Economics/Mathematical Methods</topic><topic>Economics</topic><topic>Economics and Finance</topic><topic>Game Theory</topic><topic>Games</topic><topic>Guards</topic><topic>Operations Research/Decision Theory</topic><topic>Original Paper</topic><topic>Social and Behav. Sciences</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Finbow, Stephen</creatorcontrib><creatorcontrib>Gaspers, Serge</creatorcontrib><creatorcontrib>Messinger, Margaret-Ellen</creatorcontrib><creatorcontrib>Ottaway, Paul</creatorcontrib><collection>CrossRef</collection><collection>ProQuest Central (Corporate)</collection><collection>ABI/INFORM Collection</collection><collection>ABI/INFORM Global (PDF only)</collection><collection>ProQuest Central (purchase pre-March 2016)</collection><collection>ABI/INFORM Collection</collection><collection>Science Database (Alumni Edition)</collection><collection>ProQuest Pharma Collection</collection><collection>International Bibliography of the Social Sciences (IBSS)</collection><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>ProQuest Central (Alumni) (purchase pre-March 2016)</collection><collection>ABI/INFORM Collection (Alumni Edition)</collection><collection>Research Library (Alumni Edition)</collection><collection>Materials Science &amp; Engineering Collection</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central</collection><collection>Advanced Technologies &amp; Aerospace Collection</collection><collection>ProQuest Central Essentials</collection><collection>ProQuest Central</collection><collection>Business Premium Collection</collection><collection>Technology Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest Central Korea</collection><collection>International Bibliography of the Social Sciences</collection><collection>Business Premium Collection (Alumni)</collection><collection>ABI/INFORM Global (Corporate)</collection><collection>ProQuest Central Student</collection><collection>Research Library Prep</collection><collection>SciTech Premium Collection</collection><collection>International Bibliography of the Social Sciences</collection><collection>ProQuest Computer Science Collection</collection><collection>ProQuest Business Collection (Alumni Edition)</collection><collection>ProQuest Business Collection</collection><collection>Computer Science Database</collection><collection>ABI/INFORM Professional Advanced</collection><collection>ProQuest Engineering Collection</collection><collection>ABI/INFORM Global</collection><collection>Research Library</collection><collection>Science Database</collection><collection>Engineering Database</collection><collection>Research Library (Corporate)</collection><collection>Advanced Technologies &amp; Aerospace Database</collection><collection>ProQuest Advanced Technologies &amp; Aerospace Collection</collection><collection>Research Library China</collection><collection>ProQuest One Business</collection><collection>ProQuest One Business (Alumni)</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><collection>Engineering Collection</collection><collection>ABI/INFORM Collection China</collection><collection>ProQuest Central Basic</collection><jtitle>International journal of game theory</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Finbow, Stephen</au><au>Gaspers, Serge</au><au>Messinger, Margaret-Ellen</au><au>Ottaway, Paul</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>A note on the eternal dominating set problem</atitle><jtitle>International journal of game theory</jtitle><stitle>Int J Game Theory</stitle><date>2018-05-01</date><risdate>2018</risdate><volume>47</volume><issue>2</issue><spage>543</spage><epage>555</epage><pages>543-555</pages><issn>0020-7276</issn><eissn>1432-1270</eissn><abstract>We consider the “all guards move” model for the eternal dominating set problem. A set of guards form a dominating set on a graph and at the beginning of each round, a vertex not in the dominating set is attacked. To defend against the attack, the guards move (each guard either passes or moves to a neighboring vertex) to form a dominating set that includes the attacked vertex. The minimum number of guards required to defend against any sequence of attacks is the “eternal domination number” of the graph. In 2005, it was conjectured [Goddard et al. (J. Combin. Math. Combin. Comput. 52:169–180, 2005)] there would be no advantage to allow multiple guards to occupy the same vertex during a round. We show this is, in fact, false. We also describe algorithms to determine the eternal domination number for both models for eternal domination and examine the related combinatorial game, which makes use of the reduced canonical form of games.</abstract><cop>Berlin/Heidelberg</cop><pub>Springer Berlin Heidelberg</pub><doi>10.1007/s00182-018-0623-0</doi><tpages>13</tpages></addata></record>
fulltext fulltext
identifier ISSN: 0020-7276
ispartof International journal of game theory, 2018-05, Vol.47 (2), p.543-555
issn 0020-7276
1432-1270
language eng
recordid cdi_proquest_journals_2035475454
source EBSCOhost Business Source Ultimate; International Bibliography of the Social Sciences (IBSS); EBSCOhost Econlit with Full Text; ABI/INFORM Global; Springer Link
subjects Algorithms
Behavioral/Experimental Economics
Cameras
Combinatorial analysis
Dominance
Economic Theory/Quantitative Economics/Mathematical Methods
Economics
Economics and Finance
Game Theory
Games
Guards
Operations Research/Decision Theory
Original Paper
Social and Behav. Sciences
title A note on the eternal dominating set problem
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-25T18%3A19%3A58IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=A%20note%20on%20the%20eternal%20dominating%20set%20problem&rft.jtitle=International%20journal%20of%20game%20theory&rft.au=Finbow,%20Stephen&rft.date=2018-05-01&rft.volume=47&rft.issue=2&rft.spage=543&rft.epage=555&rft.pages=543-555&rft.issn=0020-7276&rft.eissn=1432-1270&rft_id=info:doi/10.1007/s00182-018-0623-0&rft_dat=%3Cproquest_cross%3E2035475454%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c381t-4f27504807fa69228b39680e3b697086152d5ebd7369d2105dcc56b73e7c37a73%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2035475454&rft_id=info:pmid/&rfr_iscdi=true