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.
@article{10_37236_12175,
author = {Shipeng Wang and Liming Xiong},
title = {Forbidden pairs for traceability of 2-connected graphs},
journal = {The electronic journal of combinatorics},
year = {2025},
volume = {32},
number = {3},
doi = {10.37236/12175},
zbl = {8097633},
url = {http://geodesic.mathdoc.fr/articles/10.37236/12175/}
}
TY - JOUR
AU - Shipeng Wang
AU - Liming Xiong
TI - Forbidden pairs for traceability of 2-connected graphs
JO - The electronic journal of combinatorics
PY - 2025
VL - 32
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/12175/
DO - 10.37236/12175
ID - 10_37236_12175
ER -
%0 Journal Article
%A Shipeng Wang
%A Liming Xiong
%T Forbidden pairs for traceability of 2-connected graphs
%J The electronic journal of combinatorics
%D 2025
%V 32
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/12175/
%R 10.37236/12175
%F 10_37236_12175
Shipeng Wang; Liming Xiong. Forbidden pairs for traceability of 2-connected graphs. The electronic journal of combinatorics, Tome 32 (2025) no. 3. doi: 10.37236/12175
