Forbidden Subgraph Pairs for Traceability of Block-chains
2013
Binlong Li, Hajo Broersma, Shenggui Zhang

Metrics

  • Eye Icon 218 views
  • Download Icon 113 downloads
Metrics Icon 218 views  //  113 downloads
Forbidden Subgraph Pairs for Traceability of Block\u002Dchains Image
Abstract

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.

Full text
Show more arrow
 
More from this journal
Power Graphs: a Survey
Power Graphs: a Survey Image
🧐  Browse all from this journal

Metrics

  • Eye Icon 218 views
  • Download Icon 113 downloads
Metrics Icon 218 views  //  113 downloads