Forbidden subgraphs and the König–Egerváry property | ||
| 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 | Universidade Federal do Rio de Janeiro | |
| 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 | Universidade do Estado do Rio de Janeiro | |
| 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 | Universidad Nacional de General Sarmiento. Instituto de Ciencias | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas | |
| dc.contributor.author | Bonomo, Flavia | |
| dc.contributor.author | Dourado, Mitre C. | |
| dc.contributor.author | Duran, Guillermo Alfredo | |
| dc.contributor.author | Faria, Luerbio | |
| dc.contributor.author | Grippo, Luciano Norberto | |
| dc.contributor.author | Safe, Martin Dario | |
| dc.date.issued | 2013-11 | |
| dc.description.abstract | The matching number of a graph is the maximum size of a set of vertex-disjoint edges. The transversal number is the minimum number of vertices needed to meet every edge. A graph has the König-Egerváry property if its matching number equals its transversal number. Lovász proved a characterization of graphs having the König-Egerváry property by means of forbidden subgraphs within graphs with a perfect matching. Korach, Nguyen, and Peis proposed an extension of Lovász´s result to a characterization of all graphs having the König-Egerváry property in terms of forbidden configurations (which are certain arrangements of a subgraph and a maximum matching). In this work, we prove a characterization of graphs having the König-Egerváry property by means of forbidden subgraphs which is a strengthened version of the characterization by Korach et al. Using our characterization of graphs with the König-Egerváry property, we also prove a forbidden subgraph characterization for the class of edge-perfect graphs. | 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: Dourado, Mitre C.. Universidade Federal do Rio de Janeiro; Brasil | |
| 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: Faria, Luerbio. Universidade do Estado do Rio de Janeiro; Brasil | |
| dc.description.fil | Fil: Grippo, Luciano Norberto. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina. 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.format | application/pdf | es |
| dc.identifier.citation | Bonomo, Flavia; Dourado, Mitre C.; Duran, Guillermo Alfredo; Faria, Luerbio; Grippo, Luciano Norberto; et al.; Forbidden subgraphs and the König–Egerváry property; Elsevier Science; Discrete Applied Mathematics; 161; 16-17; 11-2013; 2380-2388 | es |
| dc.identifier.institucional | CONICET | |
| dc.identifier.issn | 0166-218X | es |
| dc.identifier.repo | CONICET Digital | |
| dc.identifier.uri | http://hdl.handle.net/11336/18841 | |
| dc.journal.ciudad | Amsterdam | es |
| dc.journal.number | 16-17 | es |
| dc.journal.pagination | 2380-2388 | 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.020 | |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/url/http://www.sciencedirect.com/science/article/pii/S0166218X13002072 | |
| dc.rights | info:eu-repo/semantics/openAccess | * |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-nd/2.5/ar/ | * |
| dc.subject | Edge-Perfect Graphs | es |
| dc.subject | Forbidden Subgraphs | es |
| dc.subject | König-Egerváry Property | es |
| dc.subject | König-Egerváry Graphs | es |
| dc.subject | Maximum Matching | 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 | Forbidden subgraphs and the König–Egerváry property | 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.22699.pdf
- Tamaño:
- 424.33 KB
- Formato:
- Adobe Portable Document Format