Metric Dimension, Minimal Doubly Resolving Sets, and the Strong Metric Dimension for Jellyfish Graph and Cocktail Party Graph

Abstract

Let <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="M1"><mml:mi mathvariant="normal">Γ</mml:mi></mml:math> be a simple connected undirected graph with vertex set <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="M2"><mml:mi>V</mml:mi><mml:mfenced open="(" close=")" separators="|"><mml:mrow><mml:mi mathvariant="normal">Γ</mml:mi></mml:mrow></mml:mfenced></mml:math> and edge set <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="M3"><mml:mi>E</mml:mi><mml:mfenced open="(" close=")" separators="|"><mml:mrow><mml:mi mathvariant="normal">Γ</mml:mi></mml:mrow></mml:mfenced></mml:math>. The metric dimension of a graph <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="M4"><mml:mi mathvariant="normal">Γ</mml:mi></mml:math> is the least number of vertices in a set with the property that the list of distances from any vertex to those in the set uniquely identifies that vertex. For an ordered subset <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="M5"><mml:mi>W</mml:mi><mml:mo>=</mml:mo><mml:mfenced open="{" close="}" separators="|"><mml:mrow><mml:msub><mml:mrow><mml:mi>w</mml:mi></mml:mrow><mml:mrow><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>w</mml:mi></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:msub><mml:mo>,</mml:mo><mml:mo>…</mml:mo><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>w</mml:mi></mml:mrow><mml:mrow><mml:mi>k</mml:mi></mml:mrow></mml:msub></mml:mrow></mml:mfenced></mml:math> of vertices in a graph <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="M6"><mml:mi mathvariant="normal">Γ</mml:mi></mml:math> and a vertex <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="M7"><mml:mi>v</mml:mi></mml:math> of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="M8"><mml:mi mathvariant="normal">Γ</mml:mi></mml:math>, the metric representation of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="M9"><mml:mi>v</mml:mi></mml:math> with respect to <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="M10"><mml:mi>W</mml:mi></mml:math> is the <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="M11"><mml:mi>k</mml:mi></mml:math>-vector <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="M12"><mml:mi>r</mml:mi><mml:mfenced open="(" close=")" separators="|"><mml:mrow><mml:mfenced open="" close="|" separators="|"><mml:mrow><mml:mi>v</mml:mi></mml:mrow></mml:mfenced><mml:mi>W</mml:mi></mml:mrow></mml:mfenced><mml:mo>=</mml:mo><mml:mfenced open="(" close=")" separators="|"><mml:mrow><mml:mi>d</mml:mi><mml:mfenced open="(" close=")" separators="|"><mml:mrow><mml:mi>v</mml:mi><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>w</mml:mi></mml:mrow><mml:mrow><mml:mn>1</mml:mn></mml:mrow></mml:msub></mml:mrow></mml:mfenced><mml:mo>,</mml:mo><mml:mi>d</mml:mi><mml:mfenced open="(" close=")" separators="|"><mml:mrow><mml:mi>v</mml:mi><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>w</mml:mi></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:msub></mml:mrow></mml:mfenced><mml:mo>,</mml:mo><mml:mo>…</mml:mo><mml:mo>,</mml:mo><mml:mi>d</mml:mi><mml:mfenced open="(" close=")" separators="|"><mml:mrow><mml:mi>v</mml:mi><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>w</mml:mi></mml:mrow><mml:mrow><mml:mi>k</mml:mi></mml:mrow></mml:msub></mml:mrow></mml:mfenced></mml:mrow></mml:mfenced></mml:math>. If every pair of distinct vertices of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="M13"><mml:mi mathvariant="normal">Γ</mml:mi></mml:math> have different metric representations, then the ordered set <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="M14"><mml:mi>W</mml:mi></mml:math> is called a resolving set of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="M15"><mml:mi mathvariant="normal">Γ</mml:mi></mml:math>. It is known that the problem of computing this invariant is NP-hard. In this paper, we consider the problem of determining the cardinality <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="M16"><mml:mi>ψ</mml:mi><mml:mfenced open="(" close=")" separators="|"><mml:mrow><mml:mi mathvariant="normal">Γ</mml:mi></mml:mrow></mml:mfenced></mml:math> of minimal doubly resolving sets of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="M17"><mml:mi mathvariant="normal">Γ</mml:mi></mml:math> and the strong metric dimension for the jellyfish graph <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="M18"><mml:mtext>JFG</mml:mtext><mml:mfenced open="(" close=")" separators="|"><mml:mrow><mml:mi>n</mml:mi><mml:mo>,</mml:mo><mml:mi>m</mml:mi></mml:mrow></mml:mfenced></mml:math> and the cocktail party graph <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="M19"><mml:mtext>CP</mml:mtext><mml:mfenced open="(" close=")" separators="|"><mml:mrow><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:mfenced></mml:math>.

Topics & Concepts