Digraphs with degree equivalent induced subdigraphs
type: Item
instance of: scholarly article
title: Digraphs with degree equivalent induced subdigraphs
zbMATH Open document ID: 0663.05030
DOI: 10.1016/0095-8956(90)90083-C
author: Qun Pan
author: Jiongsheng Li
author: Huang Daode
published in: Journal of Combinatorial Theory. Series B
publication date: 1990-01-01T00:00:00Z
review text: \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 …
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 4083655
zbMATH Keywords: isomorphic subtournaments
zbMATH Keywords: tournaments
zbMATH Keywords: subdigraphs
zbMATH Keywords: digraph
MaRDI profile type: Publication
cites work: Q5588446
cites work: On strongly homogeneous tournaments
cites work: Q3097395
cites work: Score vectors of Kotzig tournaments
Recommended article: Induced Subgraphs With Many Distinct Degrees
Recommended article: Distinct degrees in induced subgraphs
Recommended article: Induced subgraphs with many repeated degrees
Recommended article: On induced subgraphs with odd degrees
Recommended article: Q5488368
Recommended article: Q4298446
Recommended article: Q3798686
Recommended article: Degrees in a digraph whose nodes are graphs
Recommended article: Q3798688
Recommended article: Degree-equipartite graphs
description: scientific article; zbMATH DE number 4083655