Loading [MathJax]/jax/output/HTML-CSS/jax.js

Ruixia Wang ; Linxin Wu ; Wei Meng - Extremal digraphs on Meyniel-type condition for hamiltonian cycles in balanced bipartite digraphs

dmtcs:5851 - Discrete Mathematics & Theoretical Computer Science, January 20, 2022, vol. 23, no. 3 - https://doi.org/10.46298/dmtcs.5851
Extremal digraphs on Meyniel-type condition for hamiltonian cycles in balanced bipartite digraphsArticle

Authors: Ruixia Wang ; Linxin Wu ; Wei Meng

    Let D be a strong balanced digraph on 2a vertices. Adamus et al. have proved that D is hamiltonian if d(u)+d(v)3a whenever uvA(D) and vuA(D). The lower bound 3a is tight. In this paper, we shall show that the extremal digraph on this condition is two classes of digraphs that can be clearly characterized. Moreover, we also show that if d(u)+d(v)3a1 whenever uvA(D) and vuA(D), then D is traceable. The lower bound 3a1 is tight.


    Volume: vol. 23, no. 3
    Section: Graph Theory
    Published on: January 20, 2022
    Accepted on: August 23, 2021
    Submitted on: October 17, 2019
    Keywords: Mathematics - Combinatorics,05C20

    1 Document citing this article

    Consultation statistics

    This page has been seen 566 times.
    This article's PDF has been downloaded 273 times.