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
StatePublished - 2014

Fingerprint

Ores

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

Li, Binlong; Li, Binlong; Broersma, Haitze J.; Zhang, Shenggui / Heavy subgraph pairs for traceability of block-chains.

In: Discussiones mathematicae. Graph theory, Vol. 34, No. 2, 2014, p. 287-307.

Research output: Scientific - peer-reviewArticle

@article{33e0b29974f14186bb3cb9117f3e24fd,
title = "Heavy subgraph pairs for traceability of block-chains",
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.",
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",
author = "Binlong Li and Binlong Li and Broersma, {Haitze J.} and Shenggui Zhang",
note = "eemcs-eprint-24776",
year = "2014",
doi = "10.7151/dmgt.1737",
volume = "34",
pages = "287--307",
journal = "Discussiones mathematicae. Graph theory",
issn = "1234-3099",
publisher = "University of Zielona Gora",
number = "2",

}

Heavy subgraph pairs for traceability of block-chains. / Li, Binlong; Li, Binlong; Broersma, Haitze J.; Zhang, Shenggui.

In: Discussiones mathematicae. Graph theory, Vol. 34, No. 2, 2014, p. 287-307.

Research output: Scientific - peer-reviewArticle

TY - JOUR

T1 - Heavy subgraph pairs for traceability of block-chains

AU - Li,Binlong

AU - Li,Binlong

AU - Broersma,Haitze J.

AU - Zhang,Shenggui

N1 - eemcs-eprint-24776

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

KW - MSC-05C07

KW - MSC-05C38

KW - MSC-05C45

KW - EWI-24776

KW - Traceable graph

KW - IR-91190

KW - $o_{-1}$-Heavy subgraph

KW - Block-chain

KW - Forbidden subgraph

KW - METIS-304107

KW - Ore-type condition

U2 - 10.7151/dmgt.1737

DO - 10.7151/dmgt.1737

M3 - Article

VL - 34

SP - 287

EP - 307

JO - Discussiones mathematicae. Graph theory

T2 - Discussiones mathematicae. Graph theory

JF - Discussiones mathematicae. Graph theory

SN - 1234-3099

IS - 2

ER -