IMAS 23417
INSTITUTO DE INVESTIGACIONES MATEMATICAS "LUIS A. SANTALO"
Unidad Ejecutora - UE
artículos
Título:
On minimal forbidden subgraph characterizations of balanced graphs
Autor/es:
BONOMO, FLAVIA; DURAN, GUILLERMO ALFREDO; SAFE, MARTIN; WAGLER, ANNEGRET
Revista:
DISCRETE APPLIED MATHEMATICS
Editorial:
ELSEVIER SCIENCE BV
Referencias:
Lugar: Amsterdam; Año: 2013 vol. 161 p. 1925 - 1942
ISSN:
0166-218X
Resumen:
A graph is balanced if its clique-matrix contains no edge?vertex
incidence matrix of an odd chordless cycle as a submatrix. 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 graphs that belong to
one of the following graph classes: complements of bipartite graphs,
line graphs of multigraphs, and complements of line graphs of
multigraphs. These characterizations lead to linear-time recognition
algorithms for balanced graphs within the same three graph classes.
