An Introduction to (1,2) - Domination Graphs

Document Type




Format of Original

6 p.

Publication Date



Utilitas Mathematica Publishing Inc.

Source Publication

Congressus Numerantium

Source ISSN



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.


Congressus Numerantium, No. 199 (2011): 33-38. Publisher Link.