Domination graphs of regular tournaments
type: Item
instance of: scholarly article
title: Domination graphs of regular tournaments
zbMATH Open document ID: 0993.05106
DOI: 10.1016/S0012-365X(01)00289-8
author: Han Hyuk Cho
author: Suh-Ryung Kim
author: J. Richard Lundgren
published in: Discrete Mathematics
publication date: 2002-08-29T00:00:00Z
review text: The domination graph \(\text{ dom}(T)\) of a tournament \(T\) has the same vertex set as \(T\) and two vertices \(x\) and \(y\) are adjacent in \(\text{ dom}(T)\) if for each vertex \(z\not= x,y\) either \(z\) is a positive neighbour of \(x\) or \(z\) is a positive neighbour of \(y\). The authors first observe that for a regular tournament \(T\) the graph \(\text{ dom}(T)\) actually equals the so-called mixed-pair graph of \(T\). Known results on these graphs easily imply that \(\text{ dom}(T)\) of a regular tournament \(T\) is either an odd cycle or the disjoint union of at least two paths. Using known results and some new constructions the authors give necessary and sufficient conditions for the union of \(m\) even paths and \(n\) non-trivial odd paths to be the domination graph of some regular tournament.
reviewed by: Dieter Rautenbach
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 1792416
zbMATH Keywords: tournament
zbMATH Keywords: domination graph
zbMATH Keywords: mixed-pair graph
MaRDI profile type: Publication
Recommended article: Q4489202
Recommended article: Q2983530
Recommended article: Q3838217
Recommended article: Q4943524
Recommended article: Q5463549
Recommended article: Q4489248
Recommended article: The domination and competition graphs of a tournament
Recommended article: Q5466066
Recommended article: Q4430866
Recommended article: Q4374702
description: scientific article; zbMATH DE number 1792416