Artículo
On minimal forbidden subgraph characterizations of balanced graphs
Fecha de publicación:
09/2013
Editorial:
Elsevier Science
Revista:
Discrete Applied Mathematics
ISSN:
0166-218X
Idioma:
Inglés
Tipo de recurso:
Artículo publicado
Clasificación temática:
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.
Archivos asociados
Licencia
Identificadores
Colecciones
Articulos(IMAS)
Articulos de INSTITUTO DE INVESTIGACIONES MATEMATICAS "LUIS A. SANTALO"
Articulos de INSTITUTO DE INVESTIGACIONES MATEMATICAS "LUIS A. SANTALO"
Articulos(OCA CIUDAD UNIVERSITARIA)
Articulos de OFICINA DE COORDINACION ADMINISTRATIVA CIUDAD UNIVERSITARIA
Articulos de OFICINA DE COORDINACION ADMINISTRATIVA CIUDAD UNIVERSITARIA
Citación
Bonomo, Flavia; Duran, Guillermo Alfredo; Safe, Martin Dario; Wagler, Annegret K.; On minimal forbidden subgraph characterizations of balanced graphs; Elsevier Science; Discrete Applied Mathematics; 161; 13-14; 9-2013; 1925-1942
Compartir
Altmétricas
Items relacionados
Mostrando titulos relacionados por título, autor y tema.
-
Bonomo-Braberman, Flavia; Durán, Guillermo; Safe, Martin Dario ; Wagler, Annegret K. (Elsevier Science, 2020-07-15)
-
de Caria, Pablo Jesús ; Gutierrez, Marisa (Elsevier Science, 2016-09)
-
Bonomo, Flavia ; Duran, Guillermo Alfredo ; Safe, Martin Dario ; Wagler, Annegret Katrin (Discrete Mathematics and Theoretical Computer Science, 2014-03)