Sesión Matemática DiscretaDescomposición de Larson y descomposición SD-KE en grafos con Matching perfecto
Agustina Victoria Ledezma
Instituto de Matemática Aplicada San Luis (UNSL-CONICET) y Departamento de Matemática, Universidad Nacional de San Luis, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Un conjunto independiente $I_C$ es llamado conjunto independiente crítico si $$ |I_C| - |N(I_C)| \;\geq\; |J| - |N(J)| $$ para todo conjunto independiente $J$. El número de independencia crítico de un grafo es la cardinalidad de un conjunto independiente crítico máximo.
La descomposición de Larson, ver [1], particiona cualquier grafo en dos subgrafos que satisfacen las siguientes condiciones: El número de independencia y el número de independencia crítico de un subgrafo coincide. El número de independencia crítico del otro subgrafo es igual a cero. La suma de los números de independencia de los dos subgrafos es igual al número de independencia del grafo original.
Un grafo es de K\H{o}nig–Egerv'{a}ry si su número de independencia más su número de matching es igual al orden del grafo.
La descomposición SD-KE de un grafo lo particiona en dos subgrafos disjuntos: uno es de König–Egerváry, y el otro se caracteriza por el hecho de que cada vértice yace ya sea en un posy o en una flower, configuraciones introducidas por Edmonds [2], Sterboul [3] y Deming [4].
En este trabajo, demostramos que ambas descomposiciones son equivalentes para grafos con un matching perfecto.
Trabajo en conjunto con: Daniel A. Jaume (Instituto de Matemática Aplicada San Luis (UNSL-CONICET) y Departamento de Matemática, Universidad Nacional de San Luis), Kevin Pereyra (Instituto de Matemática Aplicada San Luis (UNSL-CONICET) y Departamento de Matemática, Universidad Nacional de San Luis) y Valentina Soldera (Instituto de Matemática Aplicada San Luis (UNSL-CONICET) y Departamento de Matemática, Universidad Nacional de San Luis).
Referencias
[1] Larson, C. E. (2011). The critical independence number and an independence decomposition. European Journal of Combinatorics, 32(2), 294-300.European Journal of Combinatorics, 2011, vol. 32, no 2, p. 294-300.
[2] Edmonds, J. (1965). Paths, trees, and flowers. Canadian Journal of mathematics, 17, 449-467.
[3] Sterboul, F. (1979). A characterization of the graphs in which the transversal number equals the matching number. Journal of Combinatorial Theory, Series B, 27(2), 228-229.
[4] Deming, R. W. (1979). Independence numbers of graphs-an extension of the König-Egerváry theorem. Discrete Mathematics, 27(1), 23-33.