Forbidden subgraph pairs for traceability of block-chains

Binlong Li; Hajo Broersma; Shenggui Zhang

doi:10.5614/ejgta.2013.1.1.1

Forbidden subgraph pairs for traceability of block-chains

Binlong Li, Hajo Broersma, Shenggui Zhang

Discrete Mathematics and Mathematical Programming

Research output: Contribution to journal › Article › Academic › peer-review

33 Downloads (Pure)

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 language	English
Pages (from-to)	1-10
Number of pages	10
Journal	Electronic journal of graph theory and applications
Volume	1
Issue number	1
DOIs	https://doi.org/10.5614/ejgta.2013.1.1.1
Publication status	Published - 2013

Keywords

Traceable graph
Line graph
Block-chain
Closure
Forbidden subgraph
MSC-05C45
Induced subgraph

Access to Document

10.5614/ejgta.2013.1.1.1Licence: CC BY-SA

Li2013forbiddenFinal published version, 889 KBLicence: CC BY-SA

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, Block-chain, Closure, Forbidden subgraph, MSC-05C45, Induced subgraph",

author = "Binlong Li and Hajo Broersma and Shenggui Zhang",

year = "2013",

doi = "10.5614/ejgta.2013.1.1.1",

language = "English",

volume = "1",

pages = "1--10",

journal = "Electronic journal of graph theory and applications",

issn = "2338-2287",

publisher = "Indonesian Combinatorics Society",

number = "1",

}

TY - JOUR

T1 - Forbidden subgraph pairs for traceability of block-chains

AU - Li, Binlong

AU - Broersma, Hajo

AU - Zhang, Shenggui

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 - Block-chain

KW - Closure

KW - Forbidden subgraph

KW - MSC-05C45

KW - Induced subgraph

U2 - 10.5614/ejgta.2013.1.1.1

DO - 10.5614/ejgta.2013.1.1.1

M3 - Article

SN - 2338-2287

VL - 1

SP - 1

EP - 10

JO - Electronic journal of graph theory and applications

JF - Electronic journal of graph theory and applications

IS - 1

ER -

Forbidden subgraph pairs for traceability of block-chains

Abstract

Keywords

Access to Document

Fingerprint

Cite this