𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Closure and Forbidden Pairs for Hamiltonicity

✍ Scribed by Zdeněk Ryjáček

Book ID
102585427
Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
223 KB
Volume
86
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

Let C be the claw K 1;3 and N the net, i.e. the only connected graph with degree sequence 333111. It is known (Bedrossian, Thesis, Memphis State University, USA, 1991; Faudree and Gould, Discrete Math. 173 (1997), 45-60) that if X ; Y is a pair of connected graphs, then, for any 2-connected graph G; G being XY -free implies G is hamiltonian if and only if X is the claw C and Y belongs to a finite list of graphs, one of them being the net N : For any such pair X ; Y we show that the closures of all 2connected XY -free graphs form a subclass of the class of CN -free graphs, and we fully describe their structure. # 2002 Elsevier Science (USA) Msc: 05C45; 05C75.

📜 SIMILAR VOLUMES

Hamiltonicity and forbidden subgraphs in
Hamiltonicity and forbidden subgraphs in 4-connected graphs
✍ Florian Pfender 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 121 KB

## Abstract Let __T__ be the line graph of the unique tree __F__ on 8 vertices with degree sequence (3,3,3,1,1,1,1,1), i.e., __T__ is a chain of three triangles. We show that every 4‐connected {__T__, __K__~1,3~}‐free graph has a hamiltonian cycle. © 2005 Wiley Periodicals, Inc. J Graph Theory 49:

A generalization of fan's condition and
A generalization of fan's condition and forbidden subgraph conditions for hamiltonicity
✍ Zhiquan Hu 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 591 KB

Let G be a 2-connected graph with n vertices and H be an induced subgraph of G. Denote 6 := {u E V(G): d(o) > n/2}. If there exists a pair of vertices x and y at distance 2 in H such that {x, y} c V(H)\K, then H is called degree light. Let F be the unique graph with degree sequence (1, 1,1,3,3,3). I