Heavy subgraph pairs for traceability of block-chains

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

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
81 Downloads (Pure)

Abstract

A graph is called traceable if it contains a Hamilton path, i.e., a path containing all its vertices. Let G be a graph on n vertices. We say that an induced subgraph of G is o-1-heavy if it contains two nonadjacent vertices which satisfy an Ore-type degree condition for traceability, i.e., with degree sum at least n−1 in G. A block-chain is a graph whose block graph is a path, i.e., it is either a P1, P2, or a 2-connected graph, or a graph with at least one cut vertex and exactly two end-blocks. Obviously, every traceable graph is a block-chain, but the reverse does not hold. In this paper we characterize all the pairs of connected o-1-heavy graphs that guarantee traceability of block-chains. Our main result is a common extension of earlier work on degree sum conditions, forbidden subgraph conditions and heavy subgraph conditions for traceability.
Original languageUndefined
Pages (from-to)287-307
Number of pages21
JournalDiscussiones mathematicae. Graph theory
Volume34
Issue number2
DOIs
Publication statusPublished - 2014

Keywords

  • MSC-05C07
  • MSC-05C38
  • MSC-05C45
  • EWI-24776
  • Traceable graph
  • IR-91190
  • $o_{-1}$-Heavy subgraph
  • Block-chain
  • Forbidden subgraph
  • METIS-304107
  • Ore-type condition

Cite this