UMA 2022
En 1947 Tutte demostro que un grafo $G$ tiene matching perfecto si y sólo si para todo $S\subseteq V(G)$ se cumple que $c_0(G-S)\leq |S|$, donde $c_0(G-S)$ denota la cantidad de componentes impares de $G-S$.
En este trabajo damos dos nuevas caracterizaciones de grafos con matching perfecto, la primera en función de la descomposición $F\!P$-$K\!E$ del grafo; y la segunda en función de la relación entre el número de independencia, número de matching y número de cubrimiento. Así, para todo grafo $G$, las siguientes afirmaciones son equivalentes: para todo $S\subseteq V(G)$ se cumple que $c_0(G-S)\leq |S|$; la parte $F\!P(G)$ no tiene flowers y la parte $K\!E(G)$ tiene matching perfecto; el número de independencia de $G$ es igual a dos veces el número de matching de $G$ menos el número de cubrimiento de $G$.
Trabajo en conjunto con: Daniel A. Jaume (Universidad Nacional de San Luis, Argentina) y Gonzalo Molina (Universidad Nacional de San Luis, Argentina).