IMASL   20939
INSTITUTO DE MATEMATICA APLICADA DE SAN LUIS "PROF. EZIO MARCHI"
Unidad Ejecutora - UE
congresos y reuniones científicas
Título:
On the null structure of bipartite graphs without cycles of length multiple of 4
Autor/es:
MOLINA, GONZALO; ADRIÁN PASTINE; DANIEL A. JAUME
Reunión:
Workshop; Latin American Workshop on Cliques in Graphs; 2018
Resumen:
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}