Hourglasses and Hamilton cycles in 4‐connected claw‐free graphs | Zendy

Kaiser Tomáš | Zendy; Li MingChu | Zendy; Ryjáček Zdeněk | Zendy; Xiong Liming | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

Hourglasses and Hamilton cycles in 4‐connected claw‐free graphs

Author(s) -

Kaiser Tomáš,

Li MingChu,

Ryjáček Zdeněk,

Xiong Liming

Publication year - 2005

Publication title -

journal of graph theory

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.164

H-Index - 54

eISSN - 1097-0118

pISSN - 0364-9024

DOI - 10.1002/jgt.20056

Subject(s) - combinatorics , mathematics , claw , hourglass , induced subgraph , conjecture , distance hereditary graph , hamiltonian path , hamiltonian (control theory) , chordal graph , graph , discrete mathematics , graph power , line graph , physics , mechanical engineering , mathematical optimization , astronomy , vertex (graph theory) , engineering

We show that if G is a 4‐connected claw‐free graph in which every induced hourglass subgraph S contains two non‐adjacent vertices with a common neighbor outside S , then G is hamiltonian. This extends the fact that 4‐connected claw‐free, hourglass‐free graphs are hamiltonian, thus proving a broader special case of a conjecture by Matthews and Sumner. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 267–276, 2005

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research