Implicit heavy subgraph conditions for hamiltonicity of almost distance-hereditary graphs

Wei Zheng, Hajo Broersma, Ligong Wang

科研成果: 会议稿件论文同行评审

摘要

We recently proved two new results on the hamiltonicity of almost distance-hereditary graphs, involving implicit degree conditions on claws, i.e., induced subgraphs isomorphic to K1,3. A graph G of order n is called implicit 1-heavy if at least one of the end vertices of each induced claw of G has implicit degree at least n/2, and G is called implicit claw-heavy if each induced claw of G has a pair of end vertices with implicit degree sum at least n. A graph G is said to be almost distance-hereditary if each connected induced subgraph H of G has the property dH(x, y) = dG(x, y) + 1 for any pair of vertices x, y ? V (H). We recently proved that every 2-connected implicit claw-heavy almost distance-hereditary graph is hamiltonian, and that every 3-connected implicit 1-heavy almost distance-hereditary graph is hamiltonian. These results improve two recent results due to Chen and Ning.

源语言英语
179-182
页数4
出版状态已出版 - 2019
活动16th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2018 - Paris, 法国
期限: 18 6月 201820 6月 2018

会议

会议16th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2018
国家/地区法国
Paris
时期18/06/1820/06/18

指纹

探究 'Implicit heavy subgraph conditions for hamiltonicity of almost distance-hereditary graphs' 的科研主题。它们共同构成独一无二的指纹。

引用此