Back to Search Start Over

Propagation tree decompositions and linearly independent vertices

Authors :
Lon H. Mitchell
Source :
Theoretical Computer Science. 849:159-162
Publication Year :
2021
Publisher :
Elsevier BV, 2021.

Abstract

We explore the relationship between propagation tree decompositions of a graph of a given size and the OS-sets of the same size, showing that each can generate the other. We give a short constructive proof that the OS-sets are in bijective correspondence with a subset of the propagation tree decompositions.

Details

ISSN :
03043975
Volume :
849
Database :
OpenAIRE
Journal :
Theoretical Computer Science
Accession number :
edsair.doi...........6c1831776a1fa166c5a4edf18516cd06
Full Text :
https://doi.org/10.1016/j.tcs.2020.10.016