A note on the metric dimension of subdivided thorn graphs

Source abstract

<p>For some ordered subset <span class="math"><em>W</em> = {<em>w</em><sub>1</sub>, <em>w</em><sub>2</sub>, ⋯, <em>w</em><sub><em>t</em></sub>}</span> of vertices in connected graph <span class="math"><em>G</em></span>, and for some vertex <span class="math"><em>v</em></span> in <span class="math"><em>G</em></span>, the metric representation of <span class="math"><em>v</em></span> with respect to <span class="math"><em>W</em></span> is defined as the <span class="math"><em>t</em></span>-vector <span class="math"><em>r</em>(<em>v</em>∣<em>W</em>) = {<em>d</em>(<em>v</em>, <em>w</em><sub>1</sub>), <em>d</em>(<em>v</em>, <em>w</em><sub>2</sub>), ⋯, <em>d</em>(<em>v</em>, <em>w</em><sub><em>t</em></sub>)}</span>. The set <span class="math"><em>W</em></span> is the resolving set of <span class="math"><em>G</em></span> if for every two vertices <span class="math"><em>u</em>, <em>v</em></span> in <span class="math"><em>G</em></span>, <span class="math"><em>r</em>(<em>u</em>∣<em>W</em>) ≠ <em>r</em>(<em>v</em>∣<em>W</em>)</span>. The metric dimension of <span class="math"><em>G</em></span>, denoted by <span class="math">dim(<em>G</em>)</span>, is defined as the minimum cardinality of <span class="math"><em>W</em></span>. Let <span class="math"><em>G</em></span> be a connected graph on <span class="math"><em>n</em></span> vertices. The thorn graph of <span class="math"><em>G</em></span>, denoted by <span class="math"><em>T</em><em>h</em>(<em>G</em>, <em>l</em><sub>1</sub>, <em>l</em><sub>2</sub>, ⋯, <em>l</em><sub><em>n</em></sub>)</span>, is constructed from <span class="math"><em>G</em></span> by adding <span class="math"><em>l</em><sub><em>i</em></sub></span> leaves to vertex <span class="math"><em>v</em><sub><em>i</em></sub></span> of <span class="math"><em>G</em></span>, for <span class="math"><em>l</em><sub><em>i</em></sub> ≥ 1</span> and <span class="math">1 ≤ <em>i</em> ≤ <em>n</em></span>. The subdivided-thorn graph, denoted by <span class="math"><em>T</em><em>D</em>(<em>G</em>, <em>l</em><sub>1</sub>(<em>y</em><sub>1</sub>), <em>l</em><sub>2</sub>(<em>y</em><sub>2</sub>), ⋯, <em>l</em><sub><em>n</em></sub>(<em>y</em><sub><em>n</em></sub>))</span>, is constructed by subdividing every <span class="math"><em>l</em><sub><em>i</em></sub></span> leaves of the thorn graph of <span class="math"><em>G</em></span> into a path on <span class="math"><em>y</em><sub><em>i</em></sub></span> vertices. In this paper the metric dimension of thorn of complete graph, <span class="math">dim(<em>T</em><em>h</em>(<em>K</em><sub><em>n</em></sub>, <em>l</em><sub>1</sub>, <em>l</em><sub>2</sub>, ⋯, <em>l</em><sub><em>n</em></sub>))</span>, <span class="math"><em>l</em><sub><em>i</em></sub> ≥ 1</span> are determined, partially answering the problem proposed by Iswadi et al . This paper also gives some conjectures for the lower bound of <span class="math">dim(<em>T</em><em>h</em>(<em>G</em>, <em>l</em><sub>1</sub>, <em>l</em><sub>2</sub>, ⋯, <em>l</em><sub><em>n</em></sub>))</span>, for arbitrary connected graph <span class="math"><em>G</em></span>. Next, the metric dimension of subdivided-thorn of complete graph, <span class="math">dim(<em>T</em><em>D</em>(<em>K</em><sub><em>n</em></sub>, <em>l</em><sub>1</sub>(<em>y</em><sub>1</sub>), <em>l</em><sub>2</sub>(<em>y</em><sub>2</sub>), ⋯, <em>l</em><sub><em>n</em></sub>(<em>y</em><sub><em>n</em></sub>))</span> are determined and some conjectures for the lower bound of <span class="math">dim(<em>T</em><em>h</em>(<em>G</em>, <em>l</em><sub>1</sub>(<em>y</em><sub>1</sub>), <em>l</em><sub>2</sub>(<em>y</em><sub>2</sub>), ⋯, <em>l</em><sub><em>n</em></sub>(<em>y</em><sub><em>n</em></sub>))</span> for arbit