<p>Let <i>G</i> be a connected graph. The nonlocal metric dimension of <i>G</i>, denoted by <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3369_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="67" /> </InlineMediaObject> <EquationSource Format="TEX">\(\textrm{dim}_{n \ell }(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mtext>dim</mtext> <mrow> <mi>n</mi> <mi>ℓ</mi> </mrow> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, is a concept that has been introduced as a variant of the standard metric dimension. The nonlocal metric dimension stipulates a minimum size for a set of vertices, the purpose of which is to distinguish any two non-adjacent vertices by the distance of a member from that set. Klavžar and Kuziak (Bull Malays Math Sci Soc 46(2):66, 2023) proved that <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3369_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="158" /> </InlineMediaObject> <EquationSource Format="TEX">\(\textrm{dim}_{n \ell }(G) \le \beta '(G)-1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mtext>dim</mtext> <mrow> <mi>n</mi> <mi>ℓ</mi> </mrow> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>≤</mo> <msup> <mi>β</mi> <mo>′</mo> </msup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>-</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>, for graphs <i>G</i> of girth at least 7, where <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3369_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="42" /> </InlineMediaObject> <EquationSource Format="TEX">\(\beta '(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>β</mi> <mo>′</mo> </msup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> is the size of the smallest possible edge cover of <i>G</i>. The authors have posed a question with the objective of improving this bound. The aim of this paper is to address this question. In this paper we show that this bound is satisfied for graphs with girth at least 5. In addition, for non-tree graphs <i>G</i> with girth at least 7, this bound is improved to sharp bound <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3369_Article_IEq4.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="71" /> </InlineMediaObject> <EquationSource Format="TEX">\(\beta '(G)-2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>β</mi> <mo>′</mo> </msup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>-</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>, and finally, we improve the bound to sharp bound <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3369_Article_IEq5.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="71" /> </InlineMediaObject> <EquationSource Format="TEX">\(\beta '(G)-3\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>β</mi> <mo>′</mo> </msup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>-</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation> whenever <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3369_Article_IEq6.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="55" /> </InlineMediaObject> <EquationSource Format="TEX">\(G\ne C_8\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo>≠</mo> <msub> <mi>C</mi> <mn>8</mn> </msub> </mrow> </math></EquationSource> </InlineEquation> is a non-tree graph of girth at least 8.</p>

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

Improvements in nonlocal metric dimension bounds

  • Meysam Korivand,
  • Doost Ali Mojdeh

摘要

Let G be a connected graph. The nonlocal metric dimension of G, denoted by \(\textrm{dim}_{n \ell }(G)\) dim n ( G ) , is a concept that has been introduced as a variant of the standard metric dimension. The nonlocal metric dimension stipulates a minimum size for a set of vertices, the purpose of which is to distinguish any two non-adjacent vertices by the distance of a member from that set. Klavžar and Kuziak (Bull Malays Math Sci Soc 46(2):66, 2023) proved that \(\textrm{dim}_{n \ell }(G) \le \beta '(G)-1\) dim n ( G ) β ( G ) - 1 , for graphs G of girth at least 7, where \(\beta '(G)\) β ( G ) is the size of the smallest possible edge cover of G. The authors have posed a question with the objective of improving this bound. The aim of this paper is to address this question. In this paper we show that this bound is satisfied for graphs with girth at least 5. In addition, for non-tree graphs G with girth at least 7, this bound is improved to sharp bound \(\beta '(G)-2\) β ( G ) - 2 , and finally, we improve the bound to sharp bound \(\beta '(G)-3\) β ( G ) - 3 whenever \(G\ne C_8\) G C 8 is a non-tree graph of girth at least 8.