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

Wei Zheng, Hajo Broersma, Ligong Wang

Research output: Contribution to conferencePaperpeer-review

Abstract

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.

Original languageEnglish
Pages179-182
Number of pages4
Publication statusPublished - 2019
Event16th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2018 - CNAM, Paris, France
Duration: 18 Jun 201820 Jun 2018
Conference number: 16
http://ctw18.lipn.univ-paris13.fr/

Workshop

Workshop16th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2018
Abbreviated titleCTW 2018
Country/TerritoryFrance
CityParis
Period18/06/1820/06/18
Internet address

Keywords

  • (almost) distance-hereditary graph
  • Claw-heavy
  • Hamilton cycle
  • Implicit degree
  • Induced claw

Fingerprint

Dive into the research topics of 'Implicit heavy subgraph conditions for hamiltonicity of almost distance-hereditary graphs'. Together they form a unique fingerprint.

Cite this