On Forbidden Pairs Implying Hamilton-Connectedness

Let X, Y be connected graphs. A graph G is (X,Y)‐free if G contains a copy of neither X nor Y as an induced subgraph. Pairs of connected graphs X,Y such that every 3‐connected (X,Y)‐free graph is Hamilton connected have been investigated most recently in (Guantao Chen and Ronald J. Gould, Bull. Inst...

Full description

Saved in:
Bibliographic Details
Published in:Journal of graph theory 2013-03, Vol.72 (3), p.327-345
Main Authors: Faudree, Jill R., Faudree, Ralph J., Ryjáček, Zdeněk, Vrána, Petr
Format: Article
Language:English
Subjects:
forbidden subgraphs
hamilton connected
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let X, Y be connected graphs. A graph G is (X,Y)‐free if G contains a copy of neither X nor Y as an induced subgraph. Pairs of connected graphs X,Y such that every 3‐connected (X,Y)‐free graph is Hamilton connected have been investigated most recently in (Guantao Chen and Ronald J. Gould, Bull. Inst. Combin. Appl., 29 (2000), 25–32.) [8] and (H. Broersma, R. J. Faudree, A. Huck, H. Trommel, and H. J. Veldman, J. Graph Theory, 40(2) (2002), 104–119.) [5]. This paper improves those results. Specifically, it is shown that every 3‐connected (X,Y)‐free graph is Hamilton connected for X=K1,3 and Y=P8,N1,1,3, or N1, 2, 2 and the proof of this result uses a new closure technique developed by the third and fourth authors. A discussion of restrictions on the nature of the graph Y is also included.
ISSN:0364-9024
1097-0118
DOI:10.1002/jgt.21645