Forbidden Pairs for Traceability of 2-Connected Graphs

Abstract

Let $\mathcal{H}$ be a set of connected graphs. A graph is said to be $\mathcal{H}$-free if it does not contain an induced subgraph isomorphic a member of $\mathcal{H}$. A graph is called traceable if it has a path containing all its vertices. In 1997, Faudree and Gould characterized all pairs $R$, $S$ such that every connected $\{R, S\}$-free graph is traceable. In this paper, we extend this result by considering 2-connected graphs, and characterize all pairs $R$, $S$ such that every 2-connected $\{R, S\}$-free graph is traceable. Furthermore, we characterize all 2-connected $\{K_{1,3},N_{1,3,4}\}$-free non-traceable graphs.