Digraphs with degree equivalent induced subdigraphs
\textit{M. Jean} [Recent Progress Combin., Proc. 3rd Waterloo Conf. 1968, 265-271 (1969; Zbl 0193.246)] has considered the n-tournaments with the property that all their subtournaments of order n-2 are isomorphic and proved the following result: For \(n\geq 5\), an n-tournament T has the property that all its subtournaments of order n-2 are isomorphic if and only if T is transitive or arc-homogeneous. \textit{V. Müller} and \textit{J. Pelant} [``On strongly homogeneous tournaments'', Czech. Math. J. 24, 378-391 (1974; Zbl 0317.05109)] proved the result as follows: For \(n\geq 5\), a non-transitive tournament T of order n has the property that all its subtournaments of order n-2 has the same score-list if and only if T is double regular. The unsolved problem 45 raised by A. Kotzig is as follows: Characterize the n-tournaments with the property that all their subtournaments of order n-1 are isomorphic. Lin Yucai, Huang Guoxun and Li Jiongsheng gave a construction of n-tournaments with this property and obtained a criterion for determining whether a non-negative integral vector R in non-decreasing order is the score-list of some n-tournament with this property. It is natural to consider how to extend the results on tournaments mentioned above to digraphs. We say that a digraph G of order n have the property \(D_ k\) if every induced subdigraphs of order n-k in G has the same degree sequence, where k is a given integer. In this paper, the authors first introduce the notion of L(m,n,k,\(\ell)\)- digraph, then prove that a digraph G of order n has the property \(D_ 1\) if and only if G is an L(m,n,k,\(\ell)\)-digraph. Further the authors prove that for \(n\geq 5\), the digraph G of order n has the property \(D_ 2\) if and only if G is one of the null graph, the complete symmetric digraph, the transitive n-tournament, or a doubly regular n-tournament. By our results together with Jean's theorem mentioned above, it follows that for \(n\geq 5\), the digraph G of order n has the property that all subdigraphs of order n-2 in G are isomorphic if and only if G is one of the null graph, the complete symmetric digraph, the transitive n-tournament, or an arc-homogeneous n-tournament.
scientific article; zbMATH DE number 4083655
scientific article