| Summary: | The vertex (respectively edge) metric dimension of a graph <i>G</i> is the size of a smallest vertex set in <i>G</i>, which distinguishes all pairs of vertices (respectively edges) in <i>G</i>, and it is denoted by <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>dim</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></semantics></math></inline-formula> (respectively <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>edim</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></semantics></math></inline-formula>). The upper bounds <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>dim</mi><mo>(</mo><mi>G</mi><mo>)</mo><mo>≤</mo><mn>2</mn><mi>c</mi><mo>(</mo><mi>G</mi><mo>)</mo><mo>−</mo><mn>1</mn></mrow></semantics></math></inline-formula> and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>edim</mi><mo>(</mo><mi>G</mi><mo>)</mo><mo>≤</mo><mn>2</mn><mi>c</mi><mo>(</mo><mi>G</mi><mo>)</mo><mo>−</mo><mn>1</mn><mo>,</mo></mrow></semantics></math></inline-formula> where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>c</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></semantics></math></inline-formula> denotes the cyclomatic number of <i>G</i>, were established to hold for cacti without leaves distinct from cycles, and moreover, all leafless cacti that attain the bounds were characterized. It was further conjectured that the same bounds hold for general connected graphs without leaves, and this conjecture was supported by showing that the problem reduces to 2-connected graphs. In this paper, we focus on <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mo>Θ</mo></semantics></math></inline-formula>-graphs, as the most simple 2-connected graphs distinct from the cycle, and show that the the upper bound <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>2</mn><mi>c</mi><mo>(</mo><mi>G</mi><mo>)</mo><mo>−</mo><mn>1</mn></mrow></semantics></math></inline-formula> holds for both metric dimensions of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mo>Θ</mo></semantics></math></inline-formula>-graphs; we characterize all <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mo>Θ</mo></semantics></math></inline-formula>-graphs for which the bound is attained. We conclude by conjecturing that there are no other extremal graphs for the bound <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>2</mn><mi>c</mi><mo>(</mo><mi>G</mi><mo>)</mo><mo>−</mo><mn>1</mn></mrow></semantics></math></inline-formula> in the class of leafless graphs besides already known extremal cacti and extremal <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mo>Θ</mo></semantics></math></inline-formula>-graphs mentioned here.
|
|---|