Premium
k ‐quasi‐transitive digraphs of large diameter
Author(s) -
AlvaSamos Jesús,
HernándezCruz César
Publication year - 2021
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22614
Subject(s) - digraph , combinatorics , mathematics , bipartite graph , transitive relation , partition (number theory) , vertex (graph theory) , integer (computer science) , discrete mathematics , hamiltonian (control theory) , graph , computer science , mathematical optimization , programming language
Given an integer k with k ≥ 2 , a digraph D = ( V D , A D ) is k ‐quasi‐transitive if for every u v ‐directed path of length k in D , we have ( u , v ) ∈ A D or ( v , u ) ∈ A D (or both). In this study, we prove that if k is an odd integer, k ≥ 5 , then every strong k ‐quasi‐transitive digraph of diameter at least k + 2 admits a partition of its vertex set V D = ( V 1 , V 2 ) such that D [ V 1 ] is Hamiltonian, and both D [ V 1 ] and D [ V 2 ] are semicomplete bipartite, when D is bipartite, or semicomplete, otherwise. As a consequence, for an odd integer k ≥ 3 , it is easy to prove that every non‐bipartite strong k ‐quasi‐transitive digraph with diameter at least k + 2 has a Hamiltonian path.