Hamiltonian Complete Number of Some Variants of Caterpillar Graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913768820178944 |
|---|---|
| author | Adefokun, Tayo Charles Ogundipe, Opeoluwa Lawrence Onaiwu, kingsley Nosa Ajayi, Deborah Olayide |
| author_facet | Adefokun, Tayo Charles Ogundipe, Opeoluwa Lawrence Onaiwu, kingsley Nosa Ajayi, Deborah Olayide |
| contents | A graph $G$ is said to be Hamiltonian if it contains a spanning cycle. In this work, we investigate the Hamiltonian completeness of certain classes of caterpillar graphs, which are trees with a central path to which all other vertices are adjacent. For a non-Hamiltonian graph $G$, the Hamiltonian complete number $λ_H(G)$ is the minimum number of edges that must be added to $G$ to make it Hamiltonian. We focus on both regular and irregular caterpillar graphs, deriving explicit formulas for $λ_H(G)$ in various cases. Specifically, we show that for a regular caterpillar graph $G_{n(k)}$ where each vertex on the central path is adjacent to $k$ leaves, $λ_H(G_{n(k)}) = n(k-1)$. We also explore irregular caterpillar graphs, where the number of leaves adjacent to each vertex on the central path varies, and provide bounds for $λ_H(G)$ in these cases. Our results contribute to the understanding of Hamiltonian properties in tree-like structures and have potential applications in network design and optimization. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2209_04204 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Hamiltonian Complete Number of Some Variants of Caterpillar Graphs Adefokun, Tayo Charles Ogundipe, Opeoluwa Lawrence Onaiwu, kingsley Nosa Ajayi, Deborah Olayide Combinatorics 05C45, 05C40, 05C38 A graph $G$ is said to be Hamiltonian if it contains a spanning cycle. In this work, we investigate the Hamiltonian completeness of certain classes of caterpillar graphs, which are trees with a central path to which all other vertices are adjacent. For a non-Hamiltonian graph $G$, the Hamiltonian complete number $λ_H(G)$ is the minimum number of edges that must be added to $G$ to make it Hamiltonian. We focus on both regular and irregular caterpillar graphs, deriving explicit formulas for $λ_H(G)$ in various cases. Specifically, we show that for a regular caterpillar graph $G_{n(k)}$ where each vertex on the central path is adjacent to $k$ leaves, $λ_H(G_{n(k)}) = n(k-1)$. We also explore irregular caterpillar graphs, where the number of leaves adjacent to each vertex on the central path varies, and provide bounds for $λ_H(G)$ in these cases. Our results contribute to the understanding of Hamiltonian properties in tree-like structures and have potential applications in network design and optimization. |
| title | Hamiltonian Complete Number of Some Variants of Caterpillar Graphs |
| topic | Combinatorics 05C45, 05C40, 05C38 |
| url | https://arxiv.org/abs/2209.04204 |