On the null structure of bipartite graphs without cycles of length a multiple of 4

Abstract

In this work we study the null space of bipartite graphs without cycles of length multiple of $4$, and its relation to structural properties. We decompose them into two subgraphs: $C_N(G)$ and $C_S(G)$. $C_N(G)$ has perfect matching and its adjacency matrix is nonsingular. $C_S(G)$ has a unique maximum independent set and the dimension of its null space equals the dimension of the null space of $G$. Even more, we show that the fundamental spaces of $G$ are the direct sum of the fundamental spaces of $C_N(G)$ and $C_S(G)$. We also obtain formulas relating the independence number and the matching number of a $C_{4k}$-free bipartite graph with $C_N(G)$ and $C_S(G)$, and the dimensions of the fundamental spaces. Among other results, we show that the rank of a $C_{4k}$-free bipartite graph is twice its matching number, generalizing a result for trees due to Bevis et al \cite{bevis1995ranks}, and Cvetković and Gutman \cite{D1972}. About maximum independent sets, we show that the intersection of all maximum independent sets of a $C_{4k}$-free bipartite graph coincides with the support of its null space.

20 pages, 3 figures