Abstract <p> An <i>eternal dominating set of a graph</i> isa dominating set<InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11754_2025_5363_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="19" /> </InlineMediaObject> <EquationSource Format="TEX">\(D\)</EquationSource> </InlineEquation> on which mobile guards are initially located (at most one guard is allowed onany vertex). For any infinite sequence of attacks occurring sequentially at vertices, the set<InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11754_2025_5363_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="19" /> </InlineMediaObject> <EquationSource Format="TEX">\(D\)</EquationSource> </InlineEquation> can be modified by moving the guard from an adjacent vertex to the attackedvertex, provided the attacked vertex has no guard on it at the time it is attacked. Theconfiguration of guards after each attack must induce a dominating set. The <i>eternal domination number</i> of a graph is the cardinality of itsminimum eternal dominating set. We prove that the eternal domination number of any planargraph of diameter 2 is equal to its clique covering number.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On the Eternal Domination Number of Planar Graphs with Diameter 2

  • D. S. Taletskii

摘要

Abstract

An eternal dominating set of a graph isa dominating set \(D\) on which mobile guards are initially located (at most one guard is allowed onany vertex). For any infinite sequence of attacks occurring sequentially at vertices, the set \(D\) can be modified by moving the guard from an adjacent vertex to the attackedvertex, provided the attacked vertex has no guard on it at the time it is attacked. Theconfiguration of guards after each attack must induce a dominating set. The eternal domination number of a graph is the cardinality of itsminimum eternal dominating set. We prove that the eternal domination number of any planargraph of diameter 2 is equal to its clique covering number.