2021/09/25 by Jelena Djokić, Djokić, Jelena, Olga Bodroža-Pantić +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithms and Data Compression #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2109.12432
openalex publication_date 2021/09/25 · openalex created_date 2021/12/31 · openalex updated_date 2026/07/28
Motivated to find the answers to some of the questions that have occurred in recent papers dealing with Hamiltonian cycles (abbreviated HCs) in some special classes of grid graphs we started the investigation of spanning unions of cycles, the so-called 2-factors, in these graphs (as a generalizations of HCs). For all the three types of graphs from the title and for any integer m ≥ 2 we propose an algorithm for obtaining a specially designed (transfer) digraph \cal D^*m. The problem of enumeration of 2-factors is reduced to the problem of enumerating oriented walks in this digraph. Computational results we gathered for m ≤ 17 reveal some interesting properties both for the digraphs \cal D^*m and for the sequences of numbers of 2-factors. We prove some of them for arbitrary m ≥ 2.