Sesión Matemática Discreta

C-ears y propiedades determinantales de Grafos.

Diego Gabriel Martinez

Universidad Nacional de San Luis, Instituto de Matematica Aplicada 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.

En esta charla introducimos la noción de c-ear, un camino de longitud impar que conecta dos vértices de un cubrimiento mínimo por vértices de un grafo. Comenzamos estudiando los c-earless graphs (grafos sin c-ears) y presentamos una nueva caracterización de los grafos bipartitos elementales en términos de la ausencia de c-ears (véase [1]).

Luego investigamos cómo la adición o eliminación de c-ears afecta las propiedades estructurales y determinantales de los grafos. Con este fin, definimos las sucesiones c-earless, lo que nos permite demostrar que cualquier grafo de Kőnig-Egerváry matcheable puede reducirse, mediante la eliminación sucesiva de c-ears, a un grafo bipartito elemental único (módulo copias de $K_2$).

Una consecuencia clave de esta reducción es que el permanente y el determinante (salvo el signo) de la matriz de adyacencia permanecen invariantes durante el proceso. Estos resultados ofrecen una nueva perspectiva sobre la estructura algebraica y combinatoria de los grafos de Kőnig-Egerváry matcheables.--

Trabajo en conjunto con: Daniel A. Jaume(UNSL, Instituto de Matemática Aplicada San Luis - Conicet), Cristian Panelo(UNSL) y Kevin Pereyra(UNSL, Instituto de Matemática Aplicada San Luis - Conicet).

Referencias

[1] Lovász, L., & Plummer, M. D. (2009). Matching theory (Vol. 367). American Mathematical Soc.

Ver resumen en PDF