Graphs with constant adjacency dimension

Abstract

For a set W of vertices and a vertex v in a graph G, the k-vector r2(v|W) = (aG(v,w1),⋯,aG(v,wk)) is the adjacency representation of v with respect to W, where W = {w1,⋯,wk} and aG(x,y) is the minimum of 2 and the distance between the vertices x and y. The set W is an adjacency resolving set for G if distinct vertices of G have distinct adjacency representations with respect to W. The minimum cardinality of an adjacency resolving set for G is its adjacency dimension. It is clear that the adjacency dimension of an n-vertex graph G is between 1 and n - 1. The graphs with adjacency dimension 1 and n - 1 are known. All graphs with adjacency dimension 2, and all n-vertex graphs with adjacency dimension n - 2 are studied in this paper. In terms of the diameter and order of G, a sharp upper bound is found for adjacency dimension of G. Also, a sharp lower bound for adjacency dimension of G is obtained in terms of order of G. Using these two bounds, all graphs with adjacency dimension 2, and all n-vertex graphs with adjacency dimension n - 2 are characterized. © 2022 World Scientific Publishing Company.