Domination on hyperbolic graphs Articles uri icon

publication date

  • November 2020

start page

  • 1

end page

  • 10

issue

  • 11

volume

  • 343

International Standard Serial Number (ISSN)

  • 0012-365X

Electronic International Standard Serial Number (EISSN)

  • 1872-681X

abstract

  • If k ≥ 1 and G = (V,E) is a finite connected graph,S ⊆ V is said adistance k-dominating set if every vertex v ∈ V is within distance k from some vertex of S.The distance k-domination number gammakw(G) is the minimum cardinality among all distance k-dominating sets of G. A set S ⊆ V is a total dominating set if every vertex v ∈ V satisfies deltaS(v) ≥ 1 and thetotal domination number, denoted by gammat(G), is the minimum cardinality among all total dominating sets of G. The study of hyperbolic graphs is an interesting topic since the hyperbolicity of any geodesic metric space is equivalent to the hyperbolicity of a graph related to it. In this paper we obtain relationships between the hyperbolicity constant delta (G) and some domination parameters of a graph G. The results in this work are inequalities, such as gammakw(G) ≥ 2delta(G)/(2k+1) and delta(G) ≤ gammat (G)/2+3.

keywords

  • domination theory; graphs; gromov hyperbolicity; total domination