Forbidden subgraph pairs for traceability of block-chains
| Main Authors: | Li, Binlong; Department of Applied Mathematics, Northwestern Polytechnical University, Xi'an, Shaanxi 710072, Broersma, Hajo; Faculty of EEMCS, University of Twente, P.O. Box 217, 7500 AE Enschede, Zhang, Shenggui; Department of Applied Mathematics, Northwestern Polytechnical University, Xi'an, Shaanxi 710072 |
|---|---|
| Format: | Article info application/pdf eJournal |
| Bahasa: | eng |
| Terbitan: |
GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB
, 2013
|
| Subjects: | |
| Online Access: |
http://www.ejgta.org/index.php/ejgta/article/view/14 http://www.ejgta.org/index.php/ejgta/article/view/14/1 |
Daftar Isi:
- A block-chain is a graph whose block graph is a path, i.e. it is either a $P_1$, a $P_2$, 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.