Forbidden subgraph pairs for traceability of block-chains

Binlong Li, Hajo Broersma, Shenggui Zhang


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.


forbidden subgraph, induced subgraph, block-chain, traceable graph, closure, line graph

Full Text:




  • There are currently no refbacks.

ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats