On the adjacency dimension of graphs

Abstract: 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

d_{G, 2} : V i m e s V i g h t a r r o w m a t h b b N c u p 0

, as

d_{G, 2} (x, y) = m i n d_{G} (x, y), 2,

where

d_{G} (x, y)

is the length of a shortest path between

x

and

y

and

m a t h b b N

is the set of positive integers. Then

(V, d_{G, 2})

is a metric space. We say that a set

S s u b s e t e q V

is a

k

-adjacency generator for

G

if for every two vertices

x, y i n V

, there exist at least

k

vertices

w_{1}, w_{2}, ..., w_{k} i n S

such that

d_{G,2}(x,w_i) e d_{G,2}(y,w_i),; mbox{for every}; iin {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.

Recommendations

Cited in

(16)

This page was built for publication: On the adjacency dimension of graphs