An Introduction to (1,2) - Domination Graphs
Format of Original
Utilitas Mathematica Publishing Inc.
Using the graph definition of secondary domination by S. T. Hedetniemi et al., we extend the concept to digraphs. Here, we define a (1,2)-domination graph of a digraph D, dom 1,2 (D). Given vertices x and y in a digraph D, x and y form a (1,2)-dominating pair if and only if for every other vertex z in D, z is one step away from x or y and at most two steps away from the other. The (1,2)-dominating graph of a digraph D is defined to be the graph G=(V,E), where V(G)=V(D), and xy is an edge of G whenever x and y are a (1,2)-dominating pair in D. In this paper, we restrict our results to those involving tournaments. We show instances where dom 1,2 (D)=dom(D), and where the two graphs are quite different. An algorithm is given for embedding any domination graph of a tournament into the (1,2)-domination graph of a tournament.