A Note on Long non-Hamiltonian Cycles in One Class of Digraphs

2012/09/20 by Samvel Kh. Darbinyan, Darbinyan, S. Kh., Iskandar A. Karapetyan +1 · 1 citation
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1209.4456

openalex publication_date 2012/09/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let D be a strong digraph on n≥ 4 vertices. In [3, Discrete Applied Math., 95 (1999) 77-87)], J. Bang-Jensen, Y. Guo and A. Yeo proved the following theorem: if (*) d(x)+d(y)≥ 2n-1 and min \d⁺(x)+ d^-(y),d^-(x)+ d⁺(y)\≥ n-1 for every pair of non-adjacent vertices x, y with a common in-neighbour or a common out-neighbour, then D is hamiltonian. In this note we show that: if D is not directed cycle and satisfies the condition (*), then D contains a cycle of length n-1 or n-2.

Cited by

• On Hamiltonian Bypasses in one Class of Hamiltonian Digraphs

Related

• On longest non-Hamiltonian Cycles in Digraphs with the Conditions of Bang-Jensen, Gutin and Li
• A Note on Hamiltonian Cycles in Digraphs with Large Degrees
• Sufficient conditions for a digraph to contain: a pre-Hamiltonian cycle and cycles of lengths 3 and 4
• On Hamiltonian Bypasses in one Class of Hamiltonian Digraphs
• On pre-Hamiltonian Cycles in Hamiltonian Digraphs