On the connected metric dimension of graphs and their complements Academic Article

abstract

• Let [Formula: see text] be a graph with vertex set [Formula: see text], and let [Formula: see text] denote the length of a shortest [Formula: see text] path in [Formula: see text]. A set [Formula: see text] is called a connected resolving set of [Formula: see text] if, for any distinct [Formula: see text], there exists a vertex [Formula: see text] such that [Formula: see text], and the subgraph of [Formula: see text] induced by [Formula: see text] is connected. The connected metric dimension, [Formula: see text], of [Formula: see text] is the minimum of the cardinalities over all connected resolving sets of [Formula: see text]. For a graph [Formula: see text] and its complement [Formula: see text], each of order [Formula: see text] and connected, we conjecture that [Formula: see text]; if [Formula: see text] is a tree or a unicyclic graph, we prove the conjecture and characterize graphs achieving equality.

authors

• Yi, Eunjeong

published proceedings

• DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS

author list (cited authors)

• Yi, E.

citation count

• 0

complete list of authors

• Yi, Eunjeong

publication date

• October 2021

publisher

• World Scientific Publishing  Publisher

published in

• Discrete Mathematics, Algorithms and Applications  Journal

keywords

• (connected) Metric Dimension
• (connected) Resolving Set
• Distance
• Nordhaus-gaddum-type Result
• Trees
• Unicyclic Graphs

Digital Object Identifier (DOI)

• 10.1142/S1793830921500592

start page

• 2150059

volume

• 13

issue

• 05

URL

• http://dx.doi.org/10.1142/s1793830921500592