摘要 Abstract
若一个图 \( G \) 包含一个生成圈,则称其为Hamilton图。本文研究了一些特定类别的毛虫图(即具有中心路径且所有其他顶点均与其相邻的树)的Hamilton完备性。对于非Hamilton图 \( G \),其Hamilton完备数 \( \lambda_H(G) \) 是使 \( G \) 变为Hamilton图所需的最少添加边数。我们聚焦于正则和非正则毛虫图,并在各种情形下推导出 \( \lambda_H(G) \) 的显式公式。具体而言,对于中心路径上的每个顶点都与 \( k \) 片叶子相邻的正则毛虫图 \( G_{n(k)} \),我们证明了 \( \lambda_H(G_{n(k)}) = n(k-1) \)。此外,我们还探讨了中心路径上每个顶点相邻的叶子数量不相等的非正则毛虫图,并为这些情况下的 \( \lambda_H(G) \) 提供了界值。我们的结果有助于理解树状结构中的Hamilton性质,并在网络设计与优化中有潜在应用。
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 $\lambda_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 $\lambda_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, $\lambda_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 $\lambda_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.