Processing math: 100%

Ruixia Wang - A sufficient condition for a balanced bipartite digraph to be hamiltonian

dmtcs:1239 - Discrete Mathematics & Theoretical Computer Science, November 10, 2017, Vol. 19 no. 3 - https://doi.org/10.23638/DMTCS-19-3-11
A sufficient condition for a balanced bipartite digraph to be hamiltonianArticle

Authors: Ruixia Wang

    We describe a new type of sufficient condition for a balanced bipartite digraph to be hamiltonian. Let D be a balanced bipartite digraph and x,y be distinct vertices in D. {x,y} dominates a vertex z if xz and yz; in this case, we call the pair {x,y} dominating. In this paper, we prove that a strong balanced bipartite digraph D on 2a vertices contains a hamiltonian cycle if, for every dominating pair of vertices {x,y}, either d(x)2a1 and d(y)a+1 or d(x)a+1 and d(y)2a1. The lower bound in the result is sharp.


    Volume: Vol. 19 no. 3
    Section: Graph Theory
    Published on: November 10, 2017
    Accepted on: October 3, 2017
    Submitted on: August 16, 2016
    Keywords: Mathematics - Combinatorics,05CXX

    Consultation statistics

    This page has been seen 710 times.
    This article's PDF has been downloaded 361 times.