Document Type

Article

Language

eng

Format of Original

8 p.

Publication Date

5-11-2016

Publisher

Elsevier

Source Publication

Discrete Applied Mathematics

Source ISSN

0166-218X

Abstract

In 1980, Maurer coined the phrase king when describing any vertex of a tournament that could reach every other vertex in two or fewer steps. A (2,2)-domination graph of a digraph D, dom2,2(D), has vertex set V(D), the vertices of D, and edge uv whenever u and v each reach all other vertices of D in two or fewer steps. In this special case of the (i,j)-domination graph, we see that Maurer’s theorem plays an important role in establishing which vertices form the kings that create some of the edges in dom2,2(D). But of even more interest is that we are able to use the theorem to determine which other vertices, when paired with a king, form an edge in dom2,2(D). These vertices are referred to as heirs. Using kings and heirs, we are able to completely characterize the (2,2)-domination graphs of tournaments.

Comments

Accepted version. Discrete Applied Mathematics, Vol. 204 (May 11, 2016): 142-149. DOI. © 2016 Elsevier. Used with permission.

Available for download on Friday, May 11, 2018

Share

COinS