Non-Hamiltonian 2-regular Digraphs -- Residues

Read full text
Authors: Munagala V. Ramanath
Cited by: 0

Abstract

In earlier papers, we showed a decomposition of the arcs of 2-diregular digraphs (2-dds) and used it to prove some conditions for these graphs to be non-Hamiltonian; we then extended this decomposition to a larger class of digraphs and used it to construct infinite families of (strongly) connected non-Hamiltonian 2-dds and provided techniques to establish non-Hamiltonicity in special cases. In the present paper, for a subclass of these graphs, we show connections between non-Hamiltonicity and sets of permutations in the full symmetric group S(n) by introducing the concepts of biconjugates, excluded sets and residues; we then use these concepts to prove a necessary and sufficient condition for non-Hamiltonicity.

Fields of Study & Subjects

Advanced Graph Theory Research Advanced Combinatorial Mathematics Finite Group Theory Research

Publication details

Journal / source
arXiv (Cornell University)
Publication date
23 January 2026
Document type
Preprint