Forbidden subgraph pairs for traceability of block-chains

Binlong Li, Binlong Li, Haitze J. Broersma, Shenggui Zhang

Research output: Contribution to journalArticleAcademicpeer-review

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

Keywords

  • Traceable graph
  • Line graph
  • IR-87856
  • Block-chain
  • METIS-300018
  • Closure
  • Forbidden subgraph
  • EWI-23731
  • MSC-05C45
  • Induced subgraph

Cite this