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.
|Number of pages||10|
|Journal||Electronic journal of graph theory and applications|
|Publication status||Published - 2013|
- Traceable graph
- Line graph
- Forbidden subgraph
- Induced subgraph