Forbidden subgraph pairs for traceability of block-chains

Binlong Li (Department of Applied Mathematics, Northwestern Polytechnical University, Xi'an, Shaanxi 710072)
Hajo Broersma (Faculty of EEMCS, University of Twente, P.O. Box 217, 7500 AE Enschede)
Shenggui Zhang (Department of Applied Mathematics, Northwestern Polytechnical University, Xi'an, Shaanxi 710072)

Electronic Journal of Graph Theory and Applications (EJGTA)
Vol 1, No 1 (2013): Electronic Journal of Graph Theory and Applications

A block-chain is a graph whose block graph is a path, i.e. it is either a $P_1$, a $P_2$, or a 2-connected graph, or a graph of connectivity 1 with exactly two end-blocks. A graph is called traceable if it contains a Hamilton path. A traceable graph is clearly a block-chain, but the reverse does not hold in general.In this paper we characterize all pairs of connected graphs $\{R,S\}$ such that every $\{R,S\}$-free block-chain is traceable.