• DocumentCode
    3713218
  • Title

    On Hamiltonian bypasses in digraphs with the condition of Y. Manoussakis

  • Author

    Samvel Kh. Darbinyan

  • Author_Institution
    Institute for Informatics and Automation Problems of NAS RA, Yerevan, Armenia
  • fYear
    2015
  • Firstpage
    53
  • Lastpage
    63
  • Abstract
    Let D be a strongly connected directed graph of order n ≥ 4 which satisfies the following condition for every triple x, y, z of vertices such that x and y are nonadjacent: If there is no arc from x to z, then d(x)+d(y)+d+(x)+d-(z) ≥ 3n-2. If there is no arc from z to x, then d(x)+d(y)+d-(x)+d+(z) ≥ 3n-2. In [15] (J. of Graph Theory, Vol.16, No. 5, 51-59, 1992) Y. Manoussakis proved that D is Hamiltonian. In [9] it was shown that D contains a pre-Hamiltonian cycle (i.e., a cycle of length n-1) or n is even and D is isomorphic to the complete bipartite digraph with partite sets of cardinalities of n/2 and n/2. In this paper we show that D contains also a Hamiltonian bypass (i.e., a subdigraph is obtained from a Hamiltonian cycle by reversing exactly one arc) or D is isomorphic to one tournament of order five.
  • Keywords
    "Yttrium","Terminology","Informatics","Automation","Electronic mail","Bipartite graph"
  • Publisher
    ieee
  • Conference_Titel
    Computer Science and Information Technologies (CSIT), 2015
  • Type

    conf

  • DOI
    10.1109/CSITechnol.2015.7358250
  • Filename
    7358250