Estoy buscando el texto completo del resultado de la camarilla Moon and Moser 1965 en Cliques in Graphs (existen gráficos con un número de camarillas máximas exponenciales en ). El muro de pago de mi universidad no tiene acceso a la revista en particular. (De hecho, la vista previa proporciona las primeras oraciones de la prueba, ¡pero luego me deja sin el resto!)
Estaba interesado en este resultado relacionado con una dirección de investigación que estaba siguiendo, pero la dirección ha cambiado ligeramente, por lo que es cierto que ahora mi interés es pura curiosidad académica.
Mi pregunta es:
¿Hay un enlace al texto completo del documento en alguna parte O otro papel que bosqueje la prueba O si un bosquejo de prueba es lo suficientemente corto como para reproducirlo aquí, alguien lo sabe? Además, estoy interesado en la clase de gráficos con un número exponencial de camarillas.
Agregué el BibTeX como referencia:
@article {springerlink:10.1007/BF02760024,
author = {Moon, J. and Moser, L.},
affiliation = {University of Alberta Edmonton Canada},
title = {On cliques in graphs},
journal = {Israel Journal of Mathematics},
publisher = {Hebrew University Magnes Press},
issn = {0021-2172},
keyword = {Computer Science},
pages = {23-28},
volume = {3},
issue = {1},
url = {http://dx.doi.org/10.1007/BF02760024},
note = {10.1007/BF02760024},
year = {1965}
}
fuente
Respuestas:
fuente
También puede buscar el teorema de Moon-Moser en el libro Algoritmos exactos de Fomin-Kratsch
fuente
Las respuestas que se han dado hasta ahora son geniales. Pensé agregar algunas referencias.
Miller, RE y Muller, DE 1960. Un problema de subconjuntos máximos consistentes. Informe de investigación de IBM RC-240, Centro de investigación JT Watson, Yorktown Heights, NY.
Vatter, V. 2011. Máximos conjuntos independientes y cubiertas de separación . American Mathematical Monthly 118, 418-423.
Wood, DR 2011. Sobre el número de conjuntos independientes máximos en un gráfico . CDR abs / 1104.1243.
fuente
Aquí hay una copia del artículo de 1965 de Moon and Moser: http://users.monash.edu.au/~davidwo/MoonMoser65.pdf
Tenga en cuenta que el resultado fue probado por primera vez en 1960 por Miller y Muller: http://users.monash.edu.au/~davidwo/MillerMuller-NumberMaximalCliques.pdf
fuente