On minimal forbidden subgraph characterizations of balanced graphs
2009, Electronic Notes in Discrete Mathematics 35, 41-46, 2009Citas: 8
Agregar PDF Importar citas Importar citas SCRAPME Plots Conexiones
Autor(es)
Flavia Bonomo and Guillermo Durán and Martín D Safe and Annegret K Wagler
Abstract
A {0, 1}-matrix is balanced if it contains no square submatrix of odd order with exactly two 1's per row and per column. Balanced matrices lead to ideal formulations for both set packing and set covering problems. Balanced graphs are those graphs whose clique-vertex incidence matrix is balanced. While a forbidden induced subgraph characterization of balanced graphs is known, there is no such characterization by minimal forbidden induced subgraphs. In this work we provide minimal forbidden induced subgraph characterizations of balanced graphs restricted to some graph classes which also lead to polynomial time or even linear time recognition algorithms within the corresponding subclasses.