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

0024-3795

 In this work we study the null space of bipartite graphs without cycles of length $0$ modulo $4$ (denoted as $C_{4k}$-free bipartite graphs), and its relation to structural properties.    We extend the Null Decomposition of trees, introduced by Jaume and Molina  ($2018$), to $C_{4k}$-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: $C_N(G)$ and $C_S(G)$. $C_N$ has perfect matching number. $C_S(G)$ has a unique maximum independent set. We obtain formulas for the independence number and the matching number of a $C_{4k}$-free bipartite graph using this decomposition. We also show how the number of maximum matchings and the number of maximum independent sets in a $C_{4k}$-free biparte graph are related to its null decomposition.