The nonlocal metric dimension of a connected graph G, written as <InlineEquation ID="IEq1"> <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 the smallest possible size of a set of vertices such that allows every two non-neighbor vertices to be distinguished by the distance of a vertex from that set. In this paper, we look at some unsolved issues concerning the nonlocal metric dimension of the corona product of two graphs. In particular, we demonstrate that <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\textrm{dim}_{n \ell }(T \odot K_m) =\ell (T)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mtext>dim</mtext> <mrow> <mi>n</mi> <mi>ℓ</mi> </mrow> </msub> <mrow> <mo stretchy="false">(</mo> <mi>T</mi> <mo>⊙</mo> <msub> <mi>K</mi> <mi>m</mi> </msub> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mi>ℓ</mi> <mrow> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, where T is a tree with <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\ell (T)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ℓ</mi> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> leaves. In addition, for a connected bipartite graph G with partite sets A and B, we show that <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\textrm{dim}(G) + \min \{|A|, |B|\}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mtext>dim</mtext> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>+</mo> <mo movablelimits="true">min</mo> <mo stretchy="false">{</mo> <mo stretchy="false">|</mo> <mi>A</mi> <mo stretchy="false">|</mo> <mo>,</mo> <mo stretchy="false">|</mo> <mi>B</mi> <mo stretchy="false">|</mo> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation> is a sharp upper bound for <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\textrm{dim}_{n \ell }(G \odot K_m)$</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>⊙</mo> <msub> <mi>K</mi> <mi>m</mi> </msub> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>. We also investigate the nonlocal metric dimension of the join graph <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$G+K_1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo>+</mo> <msub> <mi>K</mi> <mn>1</mn> </msub> </mrow> </math></EquationSource> </InlineEquation> for certain graphs G, including the fan graph and a family of trees. Furthermore, a model based on integer linear programming is proposed for determining the nonlocal metric dimension. Finally, a real-world application of the nonlocal metric dimension is presented.

Nonlocal Metric Dimension: Two Operations, Integer Linear Programming and an Application

期刊论文
发表日期：

2026年4月20日

查看全文

Meysam Korivand,
Doost Ali Mojdeh,
Mostafa Tavakoli

摘要

The nonlocal metric dimension of a connected graph G, written as $\textrm{dim}_{n \ell }(G)$ ${dim}_{n ℓ} (G)$ , is the smallest possible size of a set of vertices such that allows every two non-neighbor vertices to be distinguished by the distance of a vertex from that set. In this paper, we look at some unsolved issues concerning the nonlocal metric dimension of the corona product of two graphs. In particular, we demonstrate that $\textrm{dim}_{n \ell }(T \odot K_m) =\ell (T)$ ${dim}_{n ℓ} (T ⊙ K_{m}) = ℓ (T)$ , where T is a tree with $\ell (T)$ $ℓ (T)$ leaves. In addition, for a connected bipartite graph G with partite sets A and B, we show that $\textrm{dim}(G) + \min \{|A|, |B|\}$ $dim (G) + min {| A |, | B |}$ is a sharp upper bound for $\textrm{dim}_{n \ell }(G \odot K_m)$ ${dim}_{n ℓ} (G ⊙ K_{m})$ . We also investigate the nonlocal metric dimension of the join graph $G+K_1$ $G + K_{1}$ for certain graphs G, including the fan graph and a family of trees. Furthermore, a model based on integer linear programming is proposed for determining the nonlocal metric dimension. Finally, a real-world application of the nonlocal metric dimension is presented.