Trees with a unique maximum independent set and their linear properties

Authors

  • Daniel A. Jaume Departamento de Matem´aticas, Facultad de Ciencias F´ısico-Matem´aticas y Naturales, Universidad Nacional de San Luis, and Instituto de Matem´aticas Aplicadas de San Luis, IMASL-CONICET, San Luis, Argentina
  • Gonzalo Molina Departamento de Matem´aticas, Facultad de Ciencias F´ısico-Matem´aticas y Naturales, Universidad Nacional de San Luis, San Luis, Argentina
  • Rodrigo Sota Departamento de Matem´aticas, Facultad de Ciencias F´ısico-Matem´aticas y Naturales, Universidad Nacional de San Luis, San Luis, Argentina

DOI:

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

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.

Downloads

Download data is not yet available.

References

R. B. Bapat, Graphs and Matrices, second edition, Universitext, Springer, London, 2014. MR 3289036.

J. H. Bevis, G. S. Domke and V. A. Miller, Ranks of trees and grid graphs, J. Combin. Math. Combin. Comput. 18 (1995), 109–119. MR 1334638.

R. Diestel, Graph Theory, second edition, Graduate Texts in Mathematics, 173, Springer-Verlag, New York, 2000. MR 1743598

G. Hopkins and W. Staton, Graphs with unique maximum independent sets, Discrete Math. 57 (1985), no. 3, 245–251. MR 0816813.

D. A. Jaume and G. Molina, Null decomposition of trees, Discrete Math. 341 (2018), no. 3, 836–850. MR 3754398.

C. Meyer, Matrix Analysis and Applied Linear Algebra, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, 2000. MR 1777382.

SageMath, the Sage Mathematics Software System (Version 9.3), The Sage Developers, 2019. https://www.sagemath.org/.

J. W. Sander and T. Sander, On simply structured bases of tree kernels, AKCE Int. J. Graphs Comb. 2 (2005), no. 1, 45–56. MR 2154182.

Downloads

Published

2022-06-08

Issue

Vol. 63 No. 1 (2022)

Section

Article

License

Copyright (c) 2022 Daniel A. Jaume, Gonzalo Molina, Rodrigo Sota

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

Authors who publish with this journal agree to the following terms:

Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal. The Journal may retract the paper after publication if clear evidence is found that the findings are unreliable as a result of misconduct or honest error.