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

@article{310e860110924ee0b898d1f05ac06487,
title = "Forbidden subgraph pairs for traceability of block-chains",
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.",
keywords = "Traceable graph, Line graph, IR-87856, Block-chain, METIS-300018, Closure, Forbidden subgraph, EWI-23731, MSC-05C45, Induced subgraph",
author = "Binlong Li and Binlong Li and Broersma, {Haitze J.} and Shenggui Zhang",
note = "eemcs-eprint-23731",
year = "2013",
language = "Undefined",
volume = "1",
pages = "1--10",
journal = "Electronic journal of graph theory and applications",
issn = "2338-2287",
publisher = "Indonesian Combinatorics Society",
number = "1",

}

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

In: Electronic journal of graph theory and applications, Vol. 1, No. 1, 2013, p. 1-10.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Forbidden subgraph pairs for traceability of block-chains

AU - Li, Binlong

AU - Li, Binlong

AU - Broersma, Haitze J.

AU - Zhang, Shenggui

N1 - eemcs-eprint-23731

PY - 2013

Y1 - 2013

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

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

KW - Traceable graph

KW - Line graph

KW - IR-87856

KW - Block-chain

KW - METIS-300018

KW - Closure

KW - Forbidden subgraph

KW - EWI-23731

KW - MSC-05C45

KW - Induced subgraph

M3 - Article

VL - 1

SP - 1

EP - 10

JO - Electronic journal of graph theory and applications

JF - Electronic journal of graph theory and applications

SN - 2338-2287

IS - 1

ER -