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

Authors

Kim A. S. Factor, Marquette UniversityFollow
Larry J. Langley, University of the Pacific

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

Comments

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

Recommended Citation

Factor, Kim A. S. and Langley, Larry J., "Kings and Heirs: A Characterization of the (2,2)-domination Graphs of Tournaments" (2016). Mathematics, Statistics and Computer Science Faculty Research and Publications. 478.
https://epublications.marquette.edu/mscs_fac/478