<p>Let <i>d</i> be a positive integer. The mutual <i>d</i>-visibility number <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="25_2025_2450_Article_IEq1.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="45" /> </InlineMediaObject> <EquationSource Format="TEX">\({\mu ^d}(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>μ</mi> <mi>d</mi> </msup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> of a graph <i>G</i> is introduced as the cardinality of the largest mutual <i>d</i>-visibility set. That is, <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="25_2025_2450_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="79" /> </InlineMediaObject> <EquationSource Format="TEX">\(X\subseteq V(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>X</mi> <mo>⊆</mo> <mi>V</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> is a mutual <i>d</i>-visibility set if for any pair of vertices <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="25_2025_2450_Article_IEq3.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="66" /> </InlineMediaObject> <EquationSource Format="TEX">\(x,y\in X\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>x</mi> <mo>,</mo> <mi>y</mi> <mo>∈</mo> <mi>X</mi> </mrow> </math></EquationSource> </InlineEquation>, the distance between them is larger than <i>d</i>, or there exists a shortest <i>x</i>,&#xa0;<i>y</i>-path in <i>G</i> whose internal vertices are not in <i>X</i>. Several combinatorial and computational aspects of <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="25_2025_2450_Article_IEq1.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="45" /> </InlineMediaObject> <EquationSource Format="TEX">\({\mu ^d}(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>μ</mi> <mi>d</mi> </msup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> are given in this work. Finally, the NP-completeness of the decision problem concerning finding <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="25_2025_2450_Article_IEq1.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="45" /> </InlineMediaObject> <EquationSource Format="TEX">\({\mu ^d}(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>μ</mi> <mi>d</mi> </msup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> is proved.</p>

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

Mutual d-visibility in Graphs

  • Dorota Kuziak,
  • Luis P. Montejano,
  • Juan A. Rodríguez-Velázquez

摘要

Let d be a positive integer. The mutual d-visibility number \({\mu ^d}(G)\) μ d ( G ) of a graph G is introduced as the cardinality of the largest mutual d-visibility set. That is, \(X\subseteq V(G)\) X V ( G ) is a mutual d-visibility set if for any pair of vertices \(x,y\in X\) x , y X , the distance between them is larger than d, or there exists a shortest xy-path in G whose internal vertices are not in X. Several combinatorial and computational aspects of \({\mu ^d}(G)\) μ d ( G ) are given in this work. Finally, the NP-completeness of the decision problem concerning finding \({\mu ^d}(G)\) μ d ( G ) is proved.