Score vectors of Kotzig tournaments
type: Item
instance of: scholarly article
title: Score vectors of Kotzig tournaments
zbMATH Open document ID: 0584.05039
DOI: 10.1016/0095-8956(87)90050-5
author: Yucai Lin
author: Guoxun Huang
author: Jiongsheng Li
published in: Journal of Combinatorial Theory. Series B
publication date: 1987-01-01T00:00:00Z
review text: A. Kotzig proposed the following problem: Characterize the n-tournaments with the property that all subtournaments \(T_ n-v\) are isomorphic [see ''Graph theory with applications'' (Macmillan, 1977) by \textit{J. A. Bondy} and \textit{U. S. R. Murty}]. We call them Kotzig tournaments. First, we prove that a Kotzig tournament \(T_ n\) has the structure as follows: Suppose that \(S=(s_ 1,s_ 2,...,s_ n)\) is the score vector of \(T_ n\), where \(s_ 1\leq s_ 2\leq...\leq s_ n\), and s(0),s(1),...,s(m-1) are the distinct scores of \(T_ n\), in which \(s(0)<s(1)<...<s(m-1)\), then \(n=mh\), h is odd, and (1) the induced subtournament T by the set \(V_ i\) of vertices with score s(i-1) is regular; (2) for the vertex u in \(V_ i\), let us denote \(u dom V_ j=\{(u,v):\quad v\in V_ j\},\) then \(| u dom V_ j| =(h+1)/2\), for \(1\leq j\leq i-1\) and \(| u dom V_ j| =(h-1)/2\), for \(i\leq j\leq m\); (3) for any i and j \(0\leq i\leq m-1\), \(1\leq j\leq h\), \(s_{ih+j}=(n-m)/2+i\). Next, we prove that, if \(s_ 1,s_ 2,...,s_ n\) are non-negative integers, \(s_ 1\leq s_ 2\leq...\leq s_ n\), then \(S=(s_ 1,s_ 2,...,s_ n)\) is the score vector of some Kotzig tournament if and only if for \(i=0,1,2,...,m-1\) and \(j=1,2,...,h\), \(s_{ih+j}=(n-m)/2+i\). Furthermore, we prove that if the tournament \(T_ n\) is regular, then \(T_ n\) is a Kotzig tournament if and only if the action of automorphism group of \(T_ n\) is transitive. Also, we prove that if \(T_ n\) is reducible, then \(T_ n\) is a Kotzig tournament if and only if \(T_ n\) is transitive, i.e., the score vector of \(T_ n\) is \(S=(0,1,2,...,n-1)\).
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 3935078
zbMATH Keywords: Kotzig tournaments
zbMATH Keywords: score vector
zbMATH Keywords: induced subtournament
zbMATH Keywords: isomorphic subtournament
MaRDI profile type: Publication
full work available at URL: 0095-8956(87)90050-5
OpenAlex ID: W2044728911
cites work: Q3097395
cites work: Q3929766
cites work: On Point-Symmetric Tournaments
cites work: The Theory of Round Robin Tournaments
description: scientific article; zbMATH DE number 3935078