Independence and Matching Numbers of Unicyclic Graphs From Null Space

2019/07/17 by Allem, Luiz Emilio, Jaume, Daniel Alejandro, Molina, Gonzalo +2
#05C50 #15A18 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1907.07650

Abstract

We characterize unicyclic graphs that are singular using the support of the null space of their pendant trees. From this, we obtain closed formulas for the independence and matching numbers of a unicyclic graph, based on the support of its subtrees. These formulas allows one to compute independence and matching numbers of unicyclic graphs using linear algebra methods.

Related

• Null Decomposition of Unicyclic Graphs
• On the null structure of bipartite graphs without cycles of length a multiple of 4
• On Unimodality of Independence Polynomials of Trees
• On the Core of a Unicyclic Graph
• Null Decomposition of Trees