Academic Journals Database
Disseminating quality controlled scientific knowledge

Forbidden subgraph pairs for traceability of block-chains

Author(s): Binlong Li | Hajo Broersma | Shenggui Zhang

Journal: Electronic Journal of Graph Theory and Applications
ISSN 2338-2287

Volume: 1;
Issue: 1;
Start page: 1;
Date: 2013;
Original page

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.
RPA Switzerland

RPA Switzerland

Robotic process automation


Tango Rapperswil
Tango Rapperswil