Induced subgraphs with large degrees at end-vertices for hamiltonicity of claw-free graphs
Induced subgraphs with large degrees at end-vertices for hamiltonicity of claw-free graphs
复制标题
为无爪图的哈密顿性导出端部顶点具有大度数的子图
DOI：
10.1007/s10114-016-4686-1
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Shenggui Zhang
中科院分区：
文献类型：
--
作者：
Roman Cada;B. Li;Bo Ning;Shenggui Zhang
一个图称为无爪图，如果它不包含同构于K1，3的导出子图。马修斯和萨姆纳证明了一个2-连通无爪图G是哈密尔顿图，如果它的每个顶点的度至少（|V（G）|− 2）/3.在工作坊营地; C（Novy Smokovec，1993），Broersma证明了这个结果的度条件只能限制于N（由三角形加上三条不相交的悬垂边得到的图）的诱导副本的端点。Fujisawa和Yamashita证明了马修斯和Sumner的度条件只能限制于Z 1（由三角形加上一条悬挂边得到的图）的导出副本的端点。本文的主要结果是刻划了所有的图H，使得2-连通无爪图G是Hamilton的，如果Hin G的每个导出副本的每个端点的度至少|V（G）|/3+1。这给出了一个肯定的解决方案的猜想Broersma到一个添加剂常数。
A graph is calledclaw-freeif it contains no induced subgraph isomorphic toK1,3. Matthews and Sumner proved that a 2-connected claw-free graphGis Hamiltonian if every vertex of it has degree at least (|V(G)| − 2)/3. At the workshop Camp;C (Novy Smokovec, 1993), Broersma conjectured the degree condition of this result can be restricted only to end-vertices of induced copies ofN(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 ofZ1(the graph obtained from a triangle by adding one pendant edge). Our main result in this paper is a characterization of all graphsHsuch that a 2-connected claw-free graphGis Hamiltonian if each end-vertex of every induced copy ofHinGhas degree at least |V(G)|/3+1. This gives an affirmative solution of the conjecture of Broersma up to an additive constant.