Graphs with constant adjacency dimension
Mohsen Jannesari · Discrete Mathematics Algorithms and Applications · 2021
For a set [Formula: see text] of vertices and a vertex [Formula: see text] in a graph [Formula: see text], the [Formula: see text]-vector [Formula: see text] is the adjacency representation of [Formula: see text] with respect to [Formula: see text], where [Formula: see text] and [Formula: see text] is the minimum of [Formula: see text] and the distance between the vertices [Formula: see text] and [Formula: see text]. The set [Formula: see text] is an adjacency resolving set for [Formula: see text] if distinct vertices of [Formula: see text] have distinct adjacency representations with respect to [Formula: see text]. The minimum cardinality of an adjacency resolving set for [Formula: see text] is its adjacency dimension. It is clear that the adjacency dimension of an [Formula: see text]-vertex graph [Formula: see text] is between [Formula: see text] and [Formula: see text]. The graphs with adjacency dimension [Formula: see text] and [Formula: see text] are known. All graphs with adjacency dimension [Formula: see text], and all [Formula: see text]-vertex graphs with adjacency dimension [Formula: see text] are studied in this paper. In terms of the diameter and order of [Formula: see text], a sharp upper bound is found for adjacency dimension of [Formula: see text]. Also, a sharp lower bound for adjacency dimension of [Formula: see text] is obtained in terms of order of [Formula: see text]. Using these two bounds, all graphs with adjacency dimension 2, and all [Formula: see text]-vertex graphs with adjacency dimension [Formula: see text] are characterized.