<p>In a graph <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_17_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="135" /> </InlineMediaObject> <EquationSource Format="TEX">\(G = (V(G), E(G))\)</EquationSource> </InlineEquation>, with vertex set <i>V</i>(<i>G</i>) and edge set <i>E</i>(<i>G</i>), a set <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_17_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="75" /> </InlineMediaObject> <EquationSource Format="TEX">\(S \subseteq V(G)\)</EquationSource> </InlineEquation> is said to be <i>dominating</i> if every vertex in <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_17_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="94" /> </InlineMediaObject> <EquationSource Format="TEX">\(V(G)\setminus S(G)\)</EquationSource> </InlineEquation> has at least one neighbor in <i>S</i>. The <i>domination number</i> of <i>G</i>, denoted by <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_17_Article_IEq4.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="38" /> </InlineMediaObject> <EquationSource Format="TEX">\(\gamma (G)\)</EquationSource> </InlineEquation>, is defined as the minimum cardinality among all dominating sets of <i>V</i>(<i>G</i>). Furthermore, a dominating set <i>S</i> is defined as <i>independent</i> if any two vertices in <i>S</i> are pairwise non-adjacent. The <i>independent domination number</i> of <i>G</i>, denoted by <i>i</i>(<i>G</i>), is the minimum cardinality among all independent dominating sets of <i>G</i>. Determining <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_17_Article_IEq4.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="38" /> </InlineMediaObject> <EquationSource Format="TEX">\(\gamma (G)\)</EquationSource> </InlineEquation> and <i>i</i>(<i>G</i>) for an arbitrary graph are <i>NP</i>-hard problems. In this work, we calculate the domination and independent domination numbers of two subclasses of triangle-free cubic graphs.</p>

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

Domination and Independent Domination in Some Triangle-free Cubic Graphs

  • Ben Hur Faria Reis,
  • Márcia Rodrigues Cappelle,
  • Leslie Richard Foulds

摘要

In a graph \(G = (V(G), E(G))\) , with vertex set V(G) and edge set E(G), a set \(S \subseteq V(G)\) is said to be dominating if every vertex in \(V(G)\setminus S(G)\) has at least one neighbor in S. The domination number of G, denoted by \(\gamma (G)\) , is defined as the minimum cardinality among all dominating sets of V(G). Furthermore, a dominating set S is defined as independent if any two vertices in S are pairwise non-adjacent. The independent domination number of G, denoted by i(G), is the minimum cardinality among all independent dominating sets of G. Determining \(\gamma (G)\) and i(G) for an arbitrary graph are NP-hard problems. In this work, we calculate the domination and independent domination numbers of two subclasses of triangle-free cubic graphs.