Premium
On Forbidden Pairs Implying Hamilton‐Connectedness
Author(s) -
Faudree Jill R.,
Faudree Ralph J.,
Ryjáček Zdeněk,
Vrána Petr
Publication year - 2013
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.21645
Subject(s) - combinatorics , mathematics , social connectedness , graph , induced subgraph , distance hereditary graph , connectivity , discrete mathematics , line graph , voltage graph , vertex (graph theory) , psychology , psychotherapist
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 = K 1 , 3and Y = P 8 ,N 1 , 1 , 3 , or N 1, 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.