On minimal forbidden subgraph characterizations of balanced graphs | ||
| dc.conicet.organizacion | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas | |
| dc.conicet.organizacion | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Cálculo | |
| dc.conicet.organizacion | Universidad de Chile | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas | |
| dc.conicet.organizacion | Universidad Nacional de General Sarmiento. Instituto de Ciencias | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas | |
| dc.conicet.organizacion | Universite Blaise Pascal | |
| dc.contributor.author | Bonomo, Flavia | |
| dc.contributor.author | Duran, Guillermo Alfredo | |
| dc.contributor.author | Safe, Martin Dario | |
| dc.contributor.author | Wagler, Annegret K. | |
| dc.date.issued | 2013-09 | |
| dc.description.abstract | 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. | es |
| dc.description.fil | Fil: Bonomo, Flavia. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina | |
| dc.description.fil | Fil: Duran, Guillermo Alfredo. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Cálculo; Argentina. Universidad de Chile; Chile. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina | |
| dc.description.fil | Fil: Safe, Martin Dario. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina | |
| dc.description.fil | Fil: Wagler, Annegret K.. Universite Blaise Pascal; Francia | |
| dc.format | application/pdf | es |
| dc.identifier.citation | 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 | es |
| dc.identifier.institucional | CONICET | |
| dc.identifier.issn | 0166-218X | es |
| dc.identifier.repo | CONICET Digital | |
| dc.identifier.uri | http://hdl.handle.net/11336/18827 | |
| dc.journal.ciudad | Amsterdam | es |
| dc.journal.number | 13-14 | es |
| dc.journal.pagination | 1925-1942 | es |
| dc.journal.pais | Países Bajos | es |
| dc.journal.title | Discrete Applied Mathematics | es |
| dc.journal.volume | 161 | es |
| dc.language.iso | eng | es |
| dc.publisher | Elsevier Science | es |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.dam.2013.04.001 | |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/url/http://www.sciencedirect.com/science/article/pii/S0166218X13001741 | |
| dc.rights | info:eu-repo/semantics/openAccess | * |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-nd/2.5/ar/ | * |
| dc.subject | Balanced Graphs | es |
| dc.subject | Bipartite Graphs | es |
| dc.subject | Hereditary Clique.Helly Graphs | es |
| dc.subject | Line Graphs | es |
| dc.subject | Perfect Graphs | es |
| dc.subject.classification | Matemática Aplicada | es |
| dc.subject.classification | Matemáticas | es |
| dc.subject.classification | CIENCIAS NATURALES Y EXACTAS | es |
| dc.subject.classification | Ciencias de la Computación | es |
| dc.subject.classification | Ciencias de la Computación e Información | es |
| dc.subject.classification | CIENCIAS NATURALES Y EXACTAS | es |
| dc.title | On minimal forbidden subgraph characterizations of balanced graphs | es |
| dc.type | info:eu-repo/semantics/article | |
| dc.type | info:ar-repo/semantics/artículo | |
| dc.type | info:eu-repo/semantics/publishedVersion | |
Archivos
Bloque original
Cargando...
- Nombre:
- CONICET_Digital_Nro.22698_B.pdf
- Tamaño:
- 624.4 KB
- Formato:
- Adobe Portable Document Format