Cycles through Large Degree Vertices in Digraphs: A Generalization of Meyniel's Theorem
✍ Scribed by Kenneth A. Berman; Xin Liu
- Publisher
- Elsevier Science
- Year
- 1998
- Tongue
- English
- Weight
- 191 KB
- Volume
- 74
- Category
- Article
- ISSN
- 0095-8956
No coin nor oath required. For personal study only.
✦ Synopsis
Let D=(V, E) be a digraph with vertex set V of size n and arc set E. For u # V, let d(u) denote the degree of u. A Meyniel set M is a subset of V such that d(u)+d(v) 2n&1 for every pair of nonadjacent vertices u and v belonging to M. In this paper we show that if D is strongly connected, then every Meyniel set M lies in a (directed) cycle, generalizing Meyniel's theorem. Our proof yields an O(|M| n 4 ) algorithm for finding such a cycle. As a corollary it follows that if D is strongly connected, then D contains a cycle through all vertices of degree n which generalizes a result of Shi for undirected graphs.