Forbidden subgraph pairs for traceability of block-chains
| Autor: | Binlong Li, Hajo Broersma, Shenggui Zhang |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2013 |
| Předmět: | |
| Zdroj: | Electronic Journal of Graph Theory and Applications, Vol 1, Iss 1, Pp 1-10 (2013) |
| Druh dokumentu: | article |
| ISSN: | 2338-2287 |
| DOI: | 10.5614/ejgta.2013.1.1.1 |
| Popis: | 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. |
| Databáze: | Directory of Open Access Journals |
| Externí odkaz: |
|