### Abstract

Original language | Undefined |
---|---|

Pages (from-to) | 1-10 |

Number of pages | 10 |

Journal | Electronic journal of graph theory and applications |

Volume | 1 |

Issue number | 1 |

Publication status | Published - 2013 |

### Keywords

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

### Cite this

*Electronic journal of graph theory and applications*,

*1*(1), 1-10.

}

*Electronic journal of graph theory and applications*, vol. 1, no. 1, pp. 1-10.

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

Research output: Contribution to journal › Article › Academic › peer-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 -