Bounds on the Connected Domination in Graphs

Abstract

A set S ⊆ V of a connected graph G is a hop dominating set of G if for every vertex v ∈ V S there exists a vertex u ∈ S such that d (u, v) = 2. The cardinality of a minimum hop dominating set of G is called the hop domination number and is denoted by γ_h (G). A hop dominating set D of a graph G is said to be a connected hop dominating set of G if the induced subgraph < D > is connected. The cardinality of a minimum connected hop dominating set is called the connected hop domination number of G and it is denoted by y γ_h^c (G) . In this paper some graphs G are characterized for which γ_h (G) = 2 . Bounds based on diameter, girth and maximum degree for γ_h (G)  are developed. In addition the hop domination number of wounded spider is computed. The hop dominating sets are compared to the distance-2 dominating sets. An important result is proved that if G₁^,G₂^,,,,,G_S are the connected proper subgraphs of G with minimum connected hop dominating sets D₁^,D₂^,,,,,D_S as then γ_h^c (G) ≤ γ_h^c (G i) + 2s.