Counting Traversing Hamiltonian Cycles in Tiled Graphs

Alen Vegi Kalamar ()
Additional contact information
Alen Vegi Kalamar: Department of Mathematics and Computer Science, University of Maribor, 2000 Maribor, Slovenia

Mathematics, 2023, vol. 11, issue 12, 1-13

Abstract: Recently, the problem of counting Hamiltonian cycles in 2-tiled graphs was resolved by Vegi Kalamar, Bokal, and Žerak. In this paper, we continue our research on generalized tiled graphs. We extend algorithms on counting traversing Hamiltonian cycles from 2-tiled graphs to generalized tiled graphs. We further show that, similarly as for 2-tiled graphs, for a fixed finite set of tiles, counting traversing Hamiltonian cycles can be performed in linear time with respect to the size of such graph, implying that counting traversing Hamiltonian cycles in tiled graphs is fixed-parameter tractable.

Keywords: Hamiltonian cycle; traversing Hamiltonian cycle; counting problem; tiled graph (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/12/2650/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/12/2650/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:12:p:2650-:d:1168143

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().