Superior domination in graphs

Abstract

For distinct vertices u and v of a nontrivial connected graph G, we let D_u,v = N[U] ∪ N[V]. We define a D_u,v - walk as a u-v walk in G that contains every vertex of D_u,V. The superior distance d_D(u,v) from u to v is the length of a shortest D_u,v - walk. For each vertex u ∈ V(G), define d_D-(u) = min{d _D(u,v) : v ∈ V(G) - {u}}. A vertex v (≠u) is called a superior neighbor of u if d_D(u,v) = d_D(u). A vertex u is said to superior dominate a vertex v if v is a superior neighbor of u. A set S of vertices of G is called a superior dominating set if every vertex of V(G) - S is superior dominated by some vertex in S. A superior dominating set of G of minimum cardinality is a minimum superior dominating set and its cardinality is called the superior domination number of G and is denoted by γ_sd(G). In this paper we show that for each pair of positive integers a and b, there is a connected graph G with domination number γ (G) = a and superior domination number γ_sd = b. Also we give an upper bound for the superior domination number γ_sd.