Premium
A note on vertex pancyclic oriented graphs
Author(s) -
BangJensen Jørgen,
Guo Yubao
Publication year - 1999
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/(sici)1097-0118(199908)31:4<313::aid-jgt6>3.0.co;2-c
Subject(s) - combinatorics , mathematics , pancyclic graph , vertex (graph theory) , graph , discrete mathematics , line graph , 1 planar graph
Let D be an oriented graph of order n ≥ 9, minimum degree at least n − 2, such that, for the choice of distinct vertices x and y , either xy ∈ E ( D ) or d + ( x ) + d − ( y ) ≥ n − 3. Song (J. Graph Theory 18 (1994), 461–468) proved that D is pancyclic. In this note, we give a short proof, based on Song's result, that D is, in fact, vertex pancyclic. This also generalizes a result of Jackson (J. Graph Theory 5 (1981), 147–157) for the existence of a hamiltonian cycle in oriented graphs. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 313–318, 1999