%0 Journal Article
%T Forbidden subgraph pairs for traceability of block-chains
%A Binlong Li
%A Hajo Broersma
%A Shenggui Zhang
%J Electronic Journal of Graph Theory and Applications
%D 2013
%I Indonesian Combinatorial Society (InaCombS), Graph Theory and Applications (GTA) Research Centre, The University of Newcastle, Australia, Institut Teknologi Bandung (ITB), Indonesia
%X 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.
%U http://ejgta.org/index.php/ejgta/article/view/14