Forbidden Pairs of Disconnected Graphs Implying Hamiltonicity |
| |
| Authors: | Binlong Li Petr Vrána |
| |
| Affiliation: | 1. DEPARTMENT of APPLIED MATHEMATICS, NORTHWESTERN POLYTECHNICAL UNIVERSITY, XI'AN, P. R. CHINA;2. EUROPEAN CENTRE of EXCELLENCE NTIS, UNIVERSITY of WEST BOHEMIA, PILSEN, CZECH REPUBLIC;3. DEPARTMENT of MATHEMATICS, UNIVERSITY of WEST BOHEMIA, PILSEN, CZECH REPUBLIC;4. CENTRE of EXCELLENCE ITI, CHARLES UNIVERSITY, PRAGUE, CZECH REPUBLIC |
| |
| Abstract: | 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  of graphs, the graph G is  ‐free if G is H‐free for every  . Bedrossian characterized all the pairs  of connected subgraphs such that every 2‐connected  ‐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  of (not necessarily connected) graphs such that there exists an integer n0 such that every 2‐connected  ‐free graph of order at least n0 is hamiltonian. |
| |
| Keywords: | forbidden subgraph hamiltonian graph disconnected graph |
|
|
of graphs, the graph G is 
‐free if G is H‐free for every 
. Bedrossian characterized all the pairs 
of connected subgraphs such that every 2‐connected 
‐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 
of (not necessarily connected) graphs such that there exists an integer n0 such that every 2‐connected 
‐free graph of order at least n0 is hamiltonian.