Forbidden subgraph pairs for traceability of block-chains

Binlong Li, Hajo Broersma, Shenggui Zhang

Research output: Contribution to journalArticleAcademicpeer-review

20 Downloads (Pure)


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.
Original languageEnglish
Pages (from-to)1-10
Number of pages10
JournalElectronic journal of graph theory and applications
Issue number1
Publication statusPublished - 2013


  • Traceable graph
  • Line graph
  • Block-chain
  • Closure
  • Forbidden subgraph
  • MSC-05C45
  • Induced subgraph


Dive into the research topics of 'Forbidden subgraph pairs for traceability of block-chains'. Together they form a unique fingerprint.

Cite this