### 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 | 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

Li, B., Li, B., Broersma, H. J., & Zhang, S. (2013). Forbidden subgraph pairs for traceability of block-chains.

*Electronic journal of graph theory and applications*,*1*(1), 1-10.