TY - CONF
T1 - Implicit heavy subgraph conditions for hamiltonicity of almost distance-hereditary graphs
AU - Zheng, Wei
AU - Broersma, Hajo
AU - Wang, Ligong
N1 - Publisher Copyright:
© 2019 16th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2018 - Proceedings of the Workshop.
PY - 2019
Y1 - 2019
N2 - 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.
AB - 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.
KW - (almost) distance-hereditary graph
KW - Claw-heavy
KW - Hamilton cycle
KW - Implicit degree
KW - Induced claw
UR - http://www.scopus.com/inward/record.url?scp=85075943828&partnerID=8YFLogxK
M3 - 论文
AN - SCOPUS:85075943828
SP - 179
EP - 182
T2 - 16th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2018
Y2 - 18 June 2018 through 20 June 2018
ER -