A short proof of the Chen-Manalastas theorem
type: Item
instance of: scholarly article
title: A short proof of the Chen-Manalastas theorem
zbMATH Open document ID: 0839.05078
DOI: 10.1016/0012-365X(94)00173-1
author: J. A. Bondy
published in: Discrete Mathematics
publication date: 1996-06-18T00:00:00Z
review text: The subject theorem by \textit{C. C. Chen} and \textit{P. Manalastas} [Discrete Math. 44, 243-250 (1983; Zbl 0507.05036)] states that a strong digraph \(D\) with stability number at most 2 is spanned by one circuit or by two consistent circuits (their intersection is a path). The author constructs a shorter proof of this result by first refining a result of \textit{T. Gallai} and \textit{A. N. Milgram} [Acta Sci. Math. 21, 181-186 (1960; Zbl 0101.166)] which states that if \(D\) is a digraph with stability number \(\alpha\) and \(\mathcal Q\) is a path partition of \(D\) with head set \(h({\mathcal Q})\) and tail set \(t({\mathcal Q})\) and satisfying \(|{\mathcal Q}|> \alpha\) then there is a path partition \(\mathcal P\) of \(D\) such that \(|{\mathcal P}|= |{\mathcal Q}|- 1\), \(h({\mathcal P})\subseteq h({\mathcal Q})\) and \(t({\mathcal P})\subseteq t({\mathcal Q})\).
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 825359
zbMATH Keywords: Chen-Manalastas theorem
zbMATH Keywords: digraph
zbMATH Keywords: stability number
zbMATH Keywords: circuit
zbMATH Keywords: path partition
reviewed by: R. C. Entringer
MaRDI profile type: Publication
cites work: Path Partitions in Directed Graphs
cites work: Every finite strongly connected digraph of stability 2 has a Hamiltonian path
cites work: Q3283482
cites work: Variations on the Gallai-Milgram theorem
cites work: Q3688421
cites work: Chvátal-Erdős conditions for paths and cycles in graphs and digraphs. A survey
cites work: Q4756732
full work available at URL: 0012-365x(94)00173-1
OpenAlex ID: W2030550589
description: scientific article; zbMATH DE number 825359