2018/10/13 by Jaume, Daniel A., Molina, Gonzalo, Pastine, Adrián
#05C05 #05C62 #05C69 #05C70 #15A03 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1810.05802
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: CN(G) and CS(G). CN(G) has perfect matching and its adjacency matrix is nonsingular. CS(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 CN(G) and CS(G). We also obtain formulas relating the independence number and the matching number of a C4k-free bipartite graph with CN(G) and CS(G), and the dimensions of the fundamental spaces. Among other results, we show that the rank of a C4k-free bipartite graph is twice its matching number, generalizing a result for trees due to Bevis et al \citebevis1995ranks, and Cvetković and Gutman \citeD1972. About maximum independent sets, we show that the intersection of all maximum independent sets of a C4k-free bipartite graph coincides with the support of its null space.