Paper Info
Title
Kings and Heirs: A characterization of the (2, 2)-domination graphs of tournaments.
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.
Year
DOI
Venue
2016
10.1016/j.dam.2015.10.031
Discrete Applied Mathematics
Keywords
DocType
Volume
Tournaments,Domination,Kings
Journal
204
Issue
ISSN
Citations 
C
0166-218X
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Kim A. S. Factor101.35
Larry J. Langley2145.19