Open AccessA Note on Hamiltonian Bypasses in Digraphs with Large Degrees
Author(s) -
Samvel Kh. Darbinyan
Publication year - 2020
Publication title -
mathematical problems of computer science
Language(s) - English
Resource type - Journals
eISSN - 2738-2788
pISSN - 2579-2784
DOI - 10.51408/1963-0055
Subject(s) - vertex (graph theory) , combinatorics , hamiltonian (control theory) , hamiltonian path , mathematics , hamiltonian path problem , graph , mathematical physics , discrete mathematics , physics , mathematical optimization
Let D be a 2-strongly connected directed graph of order p ≥ 3. Suppose that d(x) ≥ p for every vertex x ∈ V (D) \ {x0}, where x0 is a vertex of D. In this paper, we show that if D is Hamiltonian or d(x0) > 2(p − 1)/5, then D contains a Hamiltonian path, in which the initial vertex dominates the terminal vertex.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom