Я ищу полный текст результата клики Луны и Мозера 1965 г. О кликах в графах (существуют графы с числом максимальных клик, экспоненциальным по ). Платежная система моего университета не имеет доступа к конкретному журналу. (На самом деле, предварительный просмотр предоставляет первые несколько предложений доказательства, но затем оставляет меня без остатка!)
Меня заинтересовал этот результат, связанный с направлением исследований, которое я проводил, но направление изменилось незначительно, поэтому, по общему признанию, мой интерес теперь чисто академический интерес.
Мой вопрос:
Есть ли где-нибудь ссылка на полный текст статьи, ИЛИ другой документ, который рисует доказательство, ИЛИ, если эскиз доказательства достаточно короткий, чтобы воспроизвести его здесь, кто-нибудь знает это? Также меня интересует класс графов с экспоненциальным числом кликов.
Я добавил BibTeX для справки:
@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}
}
источник
Ответы:
источник
Вы также можете найти теорему Луны-Мозера в книге Точных алгоритмов Фомина-Крача.
источник
Ответы, которые были даны до сих пор, великолепны. Я думал, что добавлю несколько ссылок.
Миллер, RE и Мюллер, DE 1960. Проблема максимально согласованных подмножеств. Отчет об исследованиях IBM RC-240, Исследовательский центр им. Дж. Уотсона, Йорктаун-Хайтс, Нью-Йорк.
Vatter, V. 2011. Максимальные независимые множества и разделяющие покрытия . Американский математический ежемесячник 118, 418-423.
Вуд, Д.Р. 2011. О количестве максимальных независимых множеств в графе . CoRR abs / 1104.1243.
источник
Вот копия статьи 1965 года Луны и Мозера: http://users.monash.edu.au/~davidwo/MoonMoser65.pdf
Обратите внимание, что результат был фактически впервые доказан в 1960 году Миллером и Мюллером: http://users.monash.edu.au/~davidwo/MillerMuller-NumberMaximalCliques.pdf
источник