<p>Let <i>G</i> be a simple, finite and undirected graph. A set <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_28_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="75" /> </InlineMediaObject> <EquationSource Format="TEX">\(L \subseteq V(G)\)</EquationSource> </InlineEquation> is a locating-dominating set (LD-set, for short) of <i>G</i> if <i>L</i> is a dominating set of <i>G</i> and <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_28_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="161" /> </InlineMediaObject> <EquationSource Format="TEX">\(N(u) \cap L \ne N(v) \cap L\)</EquationSource> </InlineEquation> for all distinct vertices <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_28_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="123" /> </InlineMediaObject> <EquationSource Format="TEX">\(u,v \in V(G) - L\)</EquationSource> </InlineEquation>, where <i>N</i>(<i>x</i>) is the open neighborhood of <i>x</i>. The minimum cardinality of an LD-set of <i>G</i> is denoted by <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_28_Article_IEq4.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="45" /> </InlineMediaObject> <EquationSource Format="TEX">\(\gamma _L(G)\)</EquationSource> </InlineEquation>. A graph is a split graph if its vertices set can be partitioned into an independent set and a clique. We present closed formulas for <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_28_Article_IEq5.gif" Format="GIF" Height="12" Rendition="HTML" Resolution="72" Type="Linedraw" Width="21" /> </InlineMediaObject> <EquationSource Format="TEX">\(\gamma _L\)</EquationSource> </InlineEquation> in complete split graphs and split corona graphs. Moreover, we propose a way to reduce split graphs with many twin vertices.</p>

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

Locating-Dominating Sets in Some Subclasses of Split Graphs

  • Pedro Augusto Serafim Belo,
  • Márcia Rodrigues Cappelle Santana

摘要

Let G be a simple, finite and undirected graph. A set \(L \subseteq V(G)\) is a locating-dominating set (LD-set, for short) of G if L is a dominating set of G and \(N(u) \cap L \ne N(v) \cap L\) for all distinct vertices \(u,v \in V(G) - L\) , where N(x) is the open neighborhood of x. The minimum cardinality of an LD-set of G is denoted by \(\gamma _L(G)\) . A graph is a split graph if its vertices set can be partitioned into an independent set and a clique. We present closed formulas for \(\gamma _L\) in complete split graphs and split corona graphs. Moreover, we propose a way to reduce split graphs with many twin vertices.