Revista de la
Unión Matemática Argentina
Trees with a unique maximum independent set and their linear properties
Daniel A. Jaume, Gonzalo Molina, and Rodrigo Sota
Volume 63, no. 1 (2022), pp. 223–238    

https://doi.org/10.33044/revuma.1145

Download PDF

Abstract

Trees with a unique maximum independent set encode the maxi-mum matching structure in every tree. In this work we study some of their linear properties and give two graph operations, stellare and S-coalescence, which allow building all trees with a unique maximum independent set. The null space structure of any tree can be understood in terms of these graph operations.