Hamiltonian paths in iterated line graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908868676681728 |
|---|---|
| author | Ekstein, Jan Kulhánková, Zuzana |
| author_facet | Ekstein, Jan Kulhánková, Zuzana |
| contents | For integer $n$, the $n$-iterated line graph $L^n(G)$ of an undirected graph $G$ is defined to be $L(L^{n-1}(G))$, where $L^1(G)$ is the line graph $L(G)$ of $G$. In this paper we introduce hamiltonian path index. Hamiltonian path index, denoted by $h_p(G)$, is the minimum number $n$ such that $L^n(G)$ contains a hamiltonian path. We show that hamiltonian path index of $G$ exists for any graph $G$ and we set the exact value of hamiltonian path index for trees and discuss the problem about graphs with hamiltonian 2-connected blocks. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_22596 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Hamiltonian paths in iterated line graphs Ekstein, Jan Kulhánková, Zuzana Combinatorics 05C76, 05C38 For integer $n$, the $n$-iterated line graph $L^n(G)$ of an undirected graph $G$ is defined to be $L(L^{n-1}(G))$, where $L^1(G)$ is the line graph $L(G)$ of $G$. In this paper we introduce hamiltonian path index. Hamiltonian path index, denoted by $h_p(G)$, is the minimum number $n$ such that $L^n(G)$ contains a hamiltonian path. We show that hamiltonian path index of $G$ exists for any graph $G$ and we set the exact value of hamiltonian path index for trees and discuss the problem about graphs with hamiltonian 2-connected blocks. |
| title | Hamiltonian paths in iterated line graphs |
| topic | Combinatorics 05C76, 05C38 |
| url | https://arxiv.org/abs/2507.22596 |