Premium
Meyniel's theorem for strongly ( p, q ) ‐ Hamiltonian digraphs
Author(s) -
Wojda A. P.
Publication year - 1981
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190050315
Subject(s) - combinatorics , mathematics , digraph , hamiltonian (control theory) , discrete mathematics , mathematical optimization
We give the following theorem: Let D = ( V, E ) be a strongly ( p + q + 1)‐connected digraph with n ≥ p + q + 1 vertices, where p and q are nonnegative integers, p ≤ n ‐ 2, n ≥ 2. Suppose that, for each four vertices u, v, w, z (not necessarily distinct) such that { u, v } ∩ { w, z } = Ø, ( w, u ) ∉ E , ( v, z ) ∉ E , we have id ( u ) + od ( v ) + od ( w + id ( z ) ≥ 2 ( n + p + q )) + 1. Then D is strongly ( p, q )‐Hamiltonian.