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

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

Rio de Janeiro

Workshop; VIII Latin American Workshop on Cliques in Graphs; 2018

Special Committee on Algorithms, Combinatorics and Optimization (CE-ACO) of the Brazillian Computer Society (SBC).

We say that a bipartite graph without cycles of length multiple of $4$ is a $BC_{4k}$-free graphs.In this work we study the null space of $BC_{4k}$-free graphs, and its relation to structural properties. We decompose them into two different types of graphs: $N$-graphs and $S$-graphs. $N$-graphs are graphs with a perfect matching (the order of the graph is twice its matching number).$S$-graphs are graphs with a unique maximum independent set.  We relate the independence number and the matching number of a $BC_{4k}$-free graph with its $N$-graph and its $S$-graph. Among other results, we show that the rank of a $BC_{4k}$-free graph is twice its matching number, generalizing a result for trees due to Bevis et al \cite{bevis}. About maximum independent sets, we show that the intersection of all maximum independent sets of a$BC_{4k}$-free bipartite graph coincides with the support of its null space.\begin{thebibliography}{1}\bibitem{bevis}Bevis, Jean H and Domke, Gayla S and Miller, Valerie A.\newblock Ranks of trees and grid graphs.\newblock {\em J. of Combinatorial Math. and Combinatorial Computing}, 18: 109--119, 1995.\end{thebibliography}%=========================================\end{document}