Premium
The domination and competition graphs of a tournament
Author(s) -
Fisher David C.,
Lundgren J. Richard,
Merz Sarah K.,
Reid K. B.
Publication year - 1998
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199810)29:2<103::aid-jgt6>3.0.co;2-v
Subject(s) - tournament , combinatorics , mathematics , graph , complement (music) , discrete mathematics , path graph , graph power , line graph , biochemistry , chemistry , complementation , gene , phenotype
Vertices x and y dominate a tournament T if for all vertices z ≠ x , y , either x beats z or y beats z . Let dom( T ) be the graph on the vertices of T with edges between pairs of vertices that dominate T . We show that dom( T ) is either an odd cycle with possible pendant vertices or a forest of caterpillars. While this is not a characterization, it does lead to considerable information about dom( T ). Since dom( T ) is the complement of the competition graph of the tournament formed by reversing the arcs of T , complementary results are obtained for the competition graph of a tournament. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 103–110, 1998