Hamiltonian cycles and dominating cycles passing through a linear forest |
| |
Authors: | Kenta Ozeki Tomoki Yamashita |
| |
Institution: | a Department of Mathematics, Keio University, 3-14-1, Hiyoshi, Kohoku-ku, Yokohama 223-0061, Japan b Department of Mathematics, School of Dentistry, Asahi University, 1851, Hozumi, Gifu 501-0296, Japan |
| |
Abstract: | Let G be an (m+2)-graph on n vertices, and F be a linear forest in G with |E(F)|=m and ω1(F)=s, where ω1(F) is the number of components of order one in F. We denote by σ3(G) the minimum value of the degree sum of three vertices which are pairwise non-adjacent. In this paper, we give several σ3 conditions for a dominating cycle or a hamiltonian cycle passing through a linear forest. We first prove that if σ3(G)≥n+2m+2+max{s−3,0}, then every longest cycle passing through F is dominating. Using this result, we prove that if σ3(G)≥n+κ(G)+2m−1 then G contains a hamiltonian cycle passing through F. As a corollary, we obtain a result that if G is a 3-connected graph and σ3(G)≥n+κ(G)+2, then G is hamiltonian-connected. |
| |
Keywords: | Degree sum Connectivity Hamiltonian cycle Dominating cycle Linear forest |
本文献已被 ScienceDirect 等数据库收录! |
|