The adjacency dimension of graphs Articles uri icon

publication date

  • June 2022

start page

  • 1

end page

  • 16

issue

  • 3

volume

  • 22

International Standard Serial Number (ISSN)

  • 1855-3966

Electronic International Standard Serial Number (EISSN)

  • 1855-3974

abstract

  • It is known that the problem of computing the adjacency dimension of a graph is NP-hard. This suggests finding the adjacency dimension for special classes of graphs or obtaining good bounds on this invariant. In this work we obtain general bounds on the adjacency dimension of a graph G in terms of known parameters of G. We discuss the tightness of these bounds and, for some particular classes of graphs, we obtain closed formulae. In particular, we show the close relationships that exist between the adjacency dimension and other parameters, like the domination number, the location-domination number, the 2-domination number, the independent 2-domination number, the vertex cover number, the independence number and the super domination number.

subjects

  • Mathematics

keywords

  • adjacency dimension; metric dimension; location-domination number; independence number; super domination number