Forbidden Pairs of Disconnected Graphs for Traceability of Block-Chains
Wanpeng Lei, Liming Xiong, Junfeng Du, Jun Yi Yin · Symmetry · 2022
Each traceable graph must be a block-chain; however, a block-chain is not necessarily traceable in general. Whether a given graph is a block-chain or not can be easily verified by a polynomial algorithm. It occurs to us that forbidden subgraph conditions for a block-chain are traceable. In this article, we characterize all pairs of disconnected forbidden subgraphs for the traceability of block-chains, so as to completely solve pairs of forbidden subgraphs for the traceability of block-chains (including disconnected and connected).