Induced subgraphs with large degrees at end-vertices for hamiltonicity of claw-free graphs |
| |
Authors: | Roman Čada Bin Long Li Bo Ning Sheng Gui Zhang |
| |
Institution: | 1. Department of Mathematics, University of West Bohemia and Centre of Excellence ITI - Institute for Theoretical Computer Science, Charles University and European Centre of Excellence NTIS - New Technologies for the Information Society, P.O. Box 314, 306 14 Pilsen, Czech Republic;
2. Department of Applied Mathematics, Northwestern Polytechnical University, Xi'an 710072, P. R. China;
3. Center for Applied Mathematics, Tianjin University, Tianjin 300072, P. R. China |
| |
Abstract: | A graph is called claw-free if it contains no induced subgraph isomorphic to K1,3. Matthews and Sumner proved that a 2-connected claw-free graph G is Hamiltonian if every vertex of it has degree at least (|V(G)|-2)/3. At the workshop C&C (Novy Smokovec, 1993), Broersma conjectured the degree condition of this result can be restricted only to end-vertices of induced copies of N (the graph obtained from a triangle by adding three disjoint pendant edges). Fujisawa and Yamashita showed that the degree condition of Matthews and Sumner can be restricted only to end-vertices of induced copies of Z1 (the graph obtained from a triangle by adding one pendant edge). Our main result in this paper is a characterization of all graphs H such that a 2-connected claw-free graph G is Hamiltonian if each end-vertex of every induced copy of H in G has degree at least |V(G)|/3+1. This gives an affirmative solution of the conjecture of Broersma up to an additive constant. |
| |
Keywords: | Induced subgraph large degree end-vertex claw-free graph Hamiltonian graph |
本文献已被 CNKI SpringerLink 等数据库收录! |
| 点击此处可从《数学学报(英文版)》浏览原始摘要信息 |
| 点击此处可从《数学学报(英文版)》下载免费的PDF全文 |