Kings and Heirs: A Characterization of the (2,2)-Domination Graphs of Tournaments

Authors

Kim A. S. Factor, Marquette UniversityFollow
Larry L. Langley, University of the PacificFollow

Document Type

Article

Publication Title

Discrete Applied Mathematics

Department

Mathematics

ISSN

0166-218X

Volume

204

DOI

10.1016/j.dam.2015.10.031

First Page

142

Last Page

149

Publication Date

5-11-2016

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 digraphD, dom_2,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 dom_2,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 dom_2,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.

Recommended Citation

Factor, K. A., & Langley, L. L. (2016). Kings and Heirs: A Characterization of the (2,2)-Domination Graphs of Tournaments. Discrete Applied Mathematics, 204, 142–149. DOI: 10.1016/j.dam.2015.10.031
https://scholarlycommons.pacific.edu/cop-facarticles/643