On some domination parameters of butterfly graphs

Let G be a connected graph and W = {w1,w2, ...,wk} be an ordered set of vertices in G and v be an arbitrary vertex of G. The (metric) representation of v with respect to W is the k-vector r(v|W) = (d(v,w1), d(v,w2), ..., d(v,wk)), where d(x, y) represents the distance between the vertices x and y. The set W is a resolving set for G if distinct vertices of G have distinct representations with respect to W. A set S of vertices in G is a dominating set for G if every vertex of V (G) \ S is adjacent to some vertex of S. A set of vertices Dr of a graph G that is both resolving and dominating, is a resolving dominating set. The minimum cardinality of a resolving dominating set is called the resolving domination number r(G). A set Dr of vertices in G is an r-dominating set for G if every vertex of V (G) \ Dr is within the distance r from some vertex of Dr. The minimum cardinality of an r-dominating set of G is called the r-domination number of G and is denoted by r(G). A set D of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in D. We show that the resolving domination number of directed butterfly graphs is r( −−→ BF(n)) = n2n−1. Then we find the r-domination number of BF(n) specially for r = 2. Finally we prove the equality of the domination and total domination number of butterfly graphs.

Domination number, butterfly graphs, directed butterfly graphs, resolving, distance, total.