On Duality between Local Maximum Stable Sets of a Graph and its Line-Graph - Mathematics > CombinatoricsReportar como inadecuado




On Duality between Local Maximum Stable Sets of a Graph and its Line-Graph - Mathematics > Combinatorics - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: G is a Koenig-Egervary graph provided alphaG+ muG=|VG|, where muG isthe size of a maximum matching and alphaG is the cardinality of a maximumstable set.
S is a local maximum stable set of G if S is a maximum stable setof the closed neighborhood of S.
Nemhauser and Trotter Jr.
proved that anylocal maximum stable set is a subset of a maximum stable set of G.
In thispaper we demonstrate that if S is a local maximum stable set, the subgraph Hinduced by the closed neighborhood of S is a Koenig-Egervary graph, and M is amaximum matching in H, then M is a local maximum stable set in the line graphof G.



Autor: Vadim E.
Levit, Eugen Mandrescu


Fuente: https://arxiv.org/



DESCARGAR PDF




Documentos relacionados