| Title: | Counting Traversing Hamiltonian Cycles in Tiled Graphs |
|---|
| Authors: | ID Vegi Kalamar, Alen, Department of Mathematics and Computer Science, University of Maribor, 2000 Maribor, Slovenia Comtrade Gaming, 2000 Maribor, Slovenia (Author) |
|---|
| Files: |  mathematics-11-02650-v2.pdf (281,48 KB)
MD5: AC70E5D2A8F848F857E3A76F8B88E48E
 https://www.mdpi.com/2227-7390/11/12/2650/pdf
|
|---|
| Language: | English |
|---|
| Work type: | Article |
|---|
| Typology: | 1.01 - Original Scientific Article |
|---|
| Organization: | FNM - Faculty of Natural Sciences and Mathematics
|
|---|
| 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 |
|---|
| Publication status: | Published |
|---|
| Publication version: | Version of Record |
|---|
| Submitted for review: | 25.04.2023 |
|---|
| Article acceptance date: | 09.06.2023 |
|---|
| Publication date: | 10.06.2023 |
|---|
| Publisher: | MDPI |
|---|
| Year of publishing: | 2023 |
|---|
| Number of pages: | str. 2650 |
|---|
| Numbering: | Vol. 11, no. 12 |
|---|
| PID: | 20.500.12556/DKUM-86504  |
|---|
| UDC: | 519.17 |
|---|
| ISSN on article: | 2227-7390 |
|---|
| eISSN: | 2227-7390 |
|---|
| COBISS.SI-ID: | 175170051 |
|---|
| DOI: | 10.3390/math11122650 |
|---|
| Publication date in DKUM: | 04.01.2024 |
|---|
| Views: | 499 |
|---|
| Downloads: | 67 |
|---|
| Metadata: |    |
|---|
| Categories: | Misc.
|
|---|
|
:
|
Copy citation |
|---|
| | | | Average score: | (0 votes) |
|---|
| Your score: | Voting is allowed only for logged in users. |
|---|
| Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
