Navegar

Colección

Datos Estadísticas

Artículo

Dourado, M.C.; Durán, G.; Faria, L.; Grippo, L.N.; Safe, M.D. "Forbidden subgraphs and the Ko{double acute}nig property" (2011) Electronic Notes in Discrete Mathematics. 37(C):333-338
La versión final de este artículo es de uso interno. El editor solo permite incluir en el repositorio el artículo en su versión post-print. Por favor, si usted la posee enviela a
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

A graph has the Konig property if its matching number equals its transversal number. Lovász proved a characterization of graphs having the Konig property by forbidden subgraphs, restricted to 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 Konig property in terms of forbidden configurations (certain arrangements of a subgraph and a maximum matching). In this work, we prove a characterization of graphs having the Konig property in terms of forbidden subgraphs which is a strengthened version of the characterization by Korach et al. As a consequence of our characterization of graphs with the Konig property, we prove a forbidden subgraph characterization for the class of edge-perfect graphs. © 2011 Elsevier B.V.

Registro:

Documento: Artículo
Título:Forbidden subgraphs and the Ko{double acute}nig property
Autor:Dourado, M.C.; Durán, G.; Faria, L.; Grippo, L.N.; Safe, M.D.
Filiación:Instituto de Matemática, Universidade Federal do Rio de Janeiro, Brazil
CONICET, Argentina
Depto. de Matemática, FCEN, Universidad de Buenos Aires, Argentina
Depto. de Ingeniería Industrial, FCFM, Universidad de Chile, Chile
Depto. de Informática, IME, Universidade do Estado do Rio de Janeiro, Brazil
Instituto de Ciencias, Universidad Nacional de General Sarmiento, Argentina
Depto. de Computación, FCEN, Universidad de Buenos Aires, Argentina
Palabras clave:Edge-perfect graphs; Forbidden subgraphs; Ko{double acute}nig property; Ko{double acute}nig-Egerváry graphs; Maximum matching
Año:2011
Volumen:37
Número:C
Página de inicio:333
Página de fin:338
DOI: http://dx.doi.org/10.1016/j.endm.2011.05.057
Título revista:Electronic Notes in Discrete Mathematics
Título revista abreviado:Electron. Notes Discrete Math.
ISSN:15710653
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v37_nC_p333_Dourado

Referencias:

  • Deming, R.W., Independence numbers of graphs - an extension of the Konig-Egerváry theorem (1979) Discrete Math., 27, pp. 23-33
  • Dobson, M.P., Leoni, V.A., Nasini, G.L., Recognizing edge-perfect graphs: some polynomial instances, in: Proc. of the 8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, Paris, France (2009), pp. 153-156; Dobson, M.P., Leoni, V.A., Nasini, G.L., The computational complexity of the Edge-Perfect Graph and the Totally Balanced Packing Game recognition problems (2010) Electron. Notes Discrete Math., 36, pp. 551-558
  • Egerváry, J., Matrixok kombinatorikus tulajdonságairól (1931) Mat. Fiz. Lapok, 38, pp. 16-28
  • Escalante, M.S., Leoni, V.A., Nasini, G.L., A graph theoretical model for total balancedness of combinatorial games submitted to Graphs Comb (2009); Gallai, T., Über extreme Punkt- und Kantenmengen (1959) Annales Univ. Sci. Budapest., Sec. Math., 2, pp. 133-138
  • Konig, D., Graphok és matrixok (1931) Mat. Fiz. Lapok, 38, pp. 116-119
  • Korach, E., Flowers and trees in a ballet of K4, or a finite basis characterization of non-Konig-Egerváry graphs (1982), Technical Report 115, IBM-Israel Scientific Center; Korach, E., Nguyen, T., Peis, B., Subgraph characterization of red/blue-split graph and Konig-Egerváry graphs (2006), pp. 842-850. , in: Proc. of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, Miami, Florida, USA; Lovász, L., Ear-decompositions of matching-covered graphs (1983) Combinatorica, 3, pp. 105-117
  • Lovász, L., Plummer, M.D., (1986) Matching Theory, , North-Holland
  • Peis, B., "Structure Analysis of Some Generalizations of Matchings and Matroids Under Algorithmic Aspects," (2006), Ph.D. thesis, Universität zu Köln; Sterboul, F., A characterization of the graphs in which the transversal number equals the matching number (1979) J. Combin. Theory, Ser. B, 27, pp. 228-229

Citas:

---------- APA ----------
Dourado, M.C., Durán, G., Faria, L., Grippo, L.N. & Safe, M.D. (2011) . Forbidden subgraphs and the Ko{double acute}nig property. Electronic Notes in Discrete Mathematics, 37(C), 333-338.
http://dx.doi.org/10.1016/j.endm.2011.05.057
---------- CHICAGO ----------
Dourado, M.C., Durán, G., Faria, L., Grippo, L.N., Safe, M.D. "Forbidden subgraphs and the Ko{double acute}nig property" . Electronic Notes in Discrete Mathematics 37, no. C (2011) : 333-338.
http://dx.doi.org/10.1016/j.endm.2011.05.057
---------- MLA ----------
Dourado, M.C., Durán, G., Faria, L., Grippo, L.N., Safe, M.D. "Forbidden subgraphs and the Ko{double acute}nig property" . Electronic Notes in Discrete Mathematics, vol. 37, no. C, 2011, pp. 333-338.
http://dx.doi.org/10.1016/j.endm.2011.05.057
---------- VANCOUVER ----------
Dourado, M.C., Durán, G., Faria, L., Grippo, L.N., Safe, M.D. Forbidden subgraphs and the Ko{double acute}nig property. Electron. Notes Discrete Math. 2011;37(C):333-338.
http://dx.doi.org/10.1016/j.endm.2011.05.057