Null decomposition of bipartite graphs without cycles of length 0 modulo 4

JAUME, DANIEL A.; MOLINA, GONZALO; PASTINE, ADRIÁN

LINEAR ALGEBRA AND ITS APPLICATIONS

ELSEVIER SCIENCE INC

Año: 2021 vol. 614 p. 176 - 196

0024-3795

In this work we study the null space of bipartite graphs without cycles of length 0 modulo 4 (denoted as C4k-free bipartite graphs), and its relation to structural properties. We extend the Null Decomposition of trees, introduced by Jaume and Molina (2018), to C4k-free bipartite graphs. This decomposition uses the null space of the adjacency matrix of a graph G to decompose it into two different types of graphs: CN(G) and CS(G). CN has perfect matching number. CS(G) has a unique maximum independent set. We obtain formulas for the independence number and the matching number of a C4k-free bipartite graph using this decomposition. We also show how the number of maximum matchings and the number of maximum independent sets in a C4k-free bipartite graph are related to its null decomposition.