Orientations of Hamiltonian cycles in bipartite digraphs |
| |
Authors: | A. P. Wojda M. Woźniak |
| |
Affiliation: | (1) Instytut Matematyki, Akademia Górniczo-Hutnicza, Al. Mickiewicza 30, 30-059 Kraków, Poland |
| |
Abstract: | The main result of the paper is the followingTheorem. Let D=(X,Y,A) be a bipartite, balanced digraph of order 2n and size at least 2n2–2n+3. Then D contains an almost symmetric Hamiltonian cycle (i.e. a Hamiltonian cycle in which at least 2n–1 arcs are symmetric edges), unless D has a vertex which is not incident to any symmetric edge of D.This theorem implies a number of results on cycles in bipartite, balanced digraphs, including some recent results of N. Chakroun, M. Manoussakis and Y. Manoussakis. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|