Cycles through large degree vertices in digraphs: A generalization of Meyniel's theorem
type: Item
instance of: scholarly article
title: Cycles through large degree vertices in digraphs: A generalization of Meyniel's theorem
zbMATH Open document ID: 0914.05032
author: Kenneth A. Berman
author: Xin Liu
published in: Journal of Combinatorial Theory. Series B
publication date: 1999-06-07T00:00:00Z
review text: A set \(M\) of vertices of a digraph \(D\) is called a Meyniel set if \(d(u)+ d(v)\geq 2n-1\) for every pair of non-adjacent vertices belonging to \(M\) (\(n\) is the order of \(D\)). Generalizing Meyniel's theorem, the authors prove that every Meyniel set of a strongly connected digraph lies in a cycle. It is worth mentioning that insertion techniques used in the paper resemble those applied in \textit{J. Bang-Jensen}, \textit{G. Gutin} and \textit{J. Huang} [A sufficient condition for a semicomplete multipartite digraph to be Hamiltonian, Discrete Math. 161, No. 1-3, 1-12 (1996; Zbl 0870.05046)] and some other papers by J. Bang-Jensen and G. Gutin with co-authors.
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 1234254
zbMATH Keywords: digraph
zbMATH Keywords: Meyniel's theorem
zbMATH Keywords: Meyniel set
zbMATH Keywords: cycle
zbMATH Keywords: Hamiltonian
reviewed by: G. Gutin
MaRDI profile type: Publication
OpenAlex ID: W2142698005
cites work: Locally semicomplete digraphs: A generalization of tournaments
cites work: Q4888111
cites work: In-tournament digraphs
cites work: Cycles through specified vertices
cites work: Cycles containing all vertices of maximum degree
cites work: The directed subgraph homeomorphism problem
cites work: Q3266934
cites work: Cycles through vertices of large maximum degree
cites work: Une condition suffisante d'existence d'un circuit Hamiltonien dans un graphe oriente
cites work: Directed hamiltonian graphs
cites work: 2‐neighborhoods and hamiltonian conditions
cites work: Cycles containing many vertices of large degree
cites work: Sufficient Conditions for Circuits in Graphs†
DOI: 10.1006/JCTB.1998.1829
description: scientific article; zbMATH DE number 1234254