Forbidden Pairs of Disconnected Graphs Implying Hamiltonicity

详细信息    查看全文

• 作者：Binlong Li and Petr Vrá ; na
• 刊名：Journal of Graph Theory
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：84
• 期：3
• 页码：249-261
• 全文大小：295K
• ISSN：1097-0118

文摘

Let H be a given graph. A graph G is said to be H-free if G contains no induced copies of H. For a class H of graphs, the graph G is H-free if G is H-free for every H∈H. Bedrossian characterized all the pairs {R,S} of connected subgraphs such that every 2-connected {R,S}-free graph is hamiltonian. Faudree and Gould extended Bedrossian's result by proving the necessity part of the result based on infinite families of non-hamiltonian graphs. In this article, we characterize all pairs {R,S} of (not necessarily connected) graphs such that there exists an integer n₀ such that every 2-connected {R,S}-free graph of order at least n₀ is hamiltonian.