Counting Traversing Hamiltonian Cycles in Tiled Graphs
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....
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-06-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/11/12/2650 |
| _version_ | 1797593640720138240 |
|---|---|
| author | Alen Vegi Kalamar |
| author_facet | Alen Vegi Kalamar |
| author_sort | Alen Vegi Kalamar |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-11T02:12:12Z |
| format | Article |
| id | doaj.art-3411a9bb981b435c8a3f8fe13bdd1de8 |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-11T02:12:12Z |
| publishDate | 2023-06-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-3411a9bb981b435c8a3f8fe13bdd1de82023-11-18T11:27:52ZengMDPI AGMathematics2227-73902023-06-011112265010.3390/math11122650Counting Traversing Hamiltonian Cycles in Tiled GraphsAlen Vegi Kalamar0Department of Mathematics and Computer Science, University of Maribor, 2000 Maribor, SloveniaRecently, 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.https://www.mdpi.com/2227-7390/11/12/2650Hamiltonian cycletraversing Hamiltonian cyclecounting problemtiled graph |
| spellingShingle | Alen Vegi Kalamar Counting Traversing Hamiltonian Cycles in Tiled Graphs Mathematics Hamiltonian cycle traversing Hamiltonian cycle counting problem tiled graph |
| title | Counting Traversing Hamiltonian Cycles in Tiled Graphs |
| title_full | Counting Traversing Hamiltonian Cycles in Tiled Graphs |
| title_fullStr | Counting Traversing Hamiltonian Cycles in Tiled Graphs |
| title_full_unstemmed | Counting Traversing Hamiltonian Cycles in Tiled Graphs |
| title_short | Counting Traversing Hamiltonian Cycles in Tiled Graphs |
| title_sort | counting traversing hamiltonian cycles in tiled graphs |
| topic | Hamiltonian cycle traversing Hamiltonian cycle counting problem tiled graph |
| url | https://www.mdpi.com/2227-7390/11/12/2650 |
| work_keys_str_mv | AT alenvegikalamar countingtraversinghamiltoniancyclesintiledgraphs |