Domination on hyperbolic graphs

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.

Domination on hyperbolic graphs Articles