Title

An Introduction to (1,2) - Domination Graphs

Document Type

Article

Language

eng

Format of Original

6 p.

Publication Date

2011

Publisher

Utilitas Mathematica Publishing Inc.

Source Publication

Congressus Numerantium

Source ISSN

0384-9864

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.

Comments

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