On the adjacency dimension of graphs

الأصل · EN

A generator of a metric space is a set S of points in the space with the property that every point of the space is uniquely determined by its distances from the elements of S. Given a simple graph G=(V,E), we define the distance function dG,₂:V× V→ N∪ {0}, as dG,₂(x,y)={dG(x,y),2}, where dG(x,y) is the length of a shortest path between x and y and N is the set of positive integers. Then (V,dG,₂) is a metric space. We say that a set S V is a k-adjacency generator for G if for every two vertices x,y∈ V, there exist at least k vertices w₁,w₂,...,wₖ∈ S such that dG,₂(x,wᵢ)≠ dG,₂(y,wᵢ), for every i∈ {1,...,k}. A minimum cardinality k-adjacency generator is called a k-adjacency basis of G and its cardinality, the k-adjacency dimension of G. In this article we study the problem of finding the k-adjacency dimension of a graph. We give some necessary and sufficient conditions for the existence of a k-adjacency basis of an arbitrary graph G and we obtain general results on the k-adjacency dimension, including general bounds and closed formulae for some families of graphs. In particular, we obtain closed formulae for the k-adjacency dimension of join graphs G+H in terms of the k-adjacency dimension of G and H. These results concern the k-metric dimension, as join graphs have diameter two. As we can expect, the obtained results will become important tools for the study of the k-metric dimension of lexicographic product graphs and corona product graphs.