An introduction to (1,2)-domination graphs

Abstract

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.