Score vectors of Kotzig tournaments (Q1070241): Difference between revisions

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)\).