A Characterization of Connected (1, 2)-Domination Graphs of Tournaments

Abstract

Recently, Hedetniemi et al. introduced (1, 2)-domination in graphs, and the authors extended that concept to (1, 2)-domination graphs of digraphs. 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 D, dom^1,2 (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 form a (1, 2)-dominating pair in D. In this paper, we characterize all connected graphs that can be (1, 2)-dominating graphs of tournaments.

Keywords:

• tournament
• (1, 2)-dominating pair
• (1, 2)-domination graph

2010 Mathematics Subject Classification:

• 05C69