Title of article :
Forbidden subgraph pairs for traceability of block-chains
Author/Authors :
Li, Binlong Northwestern Polytechnical University - Department of Applied Mathematics, China , Li, Binlong University of Twente - Faculty of EEMCS, Netherlands , Broersma, Hajo University of Twente - Faculty of EEMCS, Netherlands , Zhang, Shenggui Northwestern Polytechnical University - Department of Applied Mathematics, China
Abstract :
A block-chain is a graph whose block graph is a path, i.e. it is either a P1, a P2, 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.
Keywords :
forbidden subgraph , induced subgraph , block , chain , traceable graph , closure , line graph
Journal title :
Electronic Journal of Graph Theory and Applications (EJGTA)
Journal title :
Electronic Journal of Graph Theory and Applications (EJGTA)
