Superior domination in graphs - Kathiresan K.M.; Marimuthu G. (Utilitas Mathematica, 2008)
For distinct vertices u and v of a nontrivial connected graph G, we let Du,v = N[U] ∪ N[V]. We define a Du,v - walk as a u-v walk in G that contains every vertex of Du,V. The superior distance dD(u,v) from u to v is the length of a shortest Du,v - walk. For each vertex u ∈ V(G), define dD-(u) = min{d D(u,v) : v ∈ V(G) - {u}}. A vertex v (≠u) is called a superior neighbor of u if dD(u,v) = dD(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.