گراف کنسر

گراف کنسر
گراف $KG_{5,2}$ با گراف پترسن ایزومورف است.
Named after	Martin Kneser
راس	$\textstyle {\binom {n}{k}}$
ضلع	$\textstyle {\binom {n}{k}}{\binom {n-k}{k}}/2$
رنگ‌آمیزی گراف	$\left\{{\begin{array}{ll}n-2k+2&n\geq 2k\\1&{\text{otherwise}}\end{array}}\right.$
ویژگی‌های	گراف منتظم arc-transitive
قراردادهای نوشتاری	KGn,k, K(n,k)

در نظریه گراف گراف کنسر (به انگلیسی: Kneser graph)،$KG_{n,k}$، گرافی است که رأس‌های آن نظیر زیرمجموعه‌های k عضوی از یک مجموعه ی n عضوی است. بین دو رأس یک یال وجود دارد اگر و تنها اگر زیرمجموعه‌های نظیر رأس‌ها ناسازگار باشند (اشتراکشان تهی باشد). این گراف‌ها به نام مارتین کنسر نامگذاری شده‌اند که برای اولین بار آنها را در سال ۱۹۵۵ بررسی کرد.

مثال‌ها

• گراف کامل n رأسی گراف نسر $KG_{n,1}$ است.
• گراف $KG_{5,2}$ با گراف پترسن ایزومورف است.

خصوصیات

• در گراف کنسر هر رأس با انتخاب k از n-k رأس دیگر مجاور است.
• همانگونه که کنسر حدس زد عدد رنگی گراف $KG_{n,k}$ دقیقاً برابر n-2k+۲ است. لوواش در سال ۱۹۷۸ و جاشوآ در سال ۲۰۰۲ برای این فرمول اثبات‌هایی توپولوژیکی ارائه دادند. در سال ۲۰۰۴ ماتوشک اثباتی کاملاً ترکیبیاتی برای آن پیدا کرد.
• وقتی n بزرگتر مساوی ۳k باشد گراف کنسر همیشه دور هامیلتونی خواهد داشت (چن ۲۰۰۰). محاسبات نشان داده‌اند که همهٔ گراف‌های همبند کسزر با nهای کوچکتر مساوی ۲۷ به جز گراف پترسن، همیلتونی هستند.
• اگر n کوچکتر از ۳k باشد گراف کنسر هیچ مثلثی نخواهد داشت.

منابع

• Wikipedia contributors, "Kneser graph," Wikipedia, The Free Encyclopedia, https://en.wikipedia.org/w/index.php?title=Kneser_graph&oldid=666391233 (accessed July 8, 2015).
• Douglas B.West (۲۰۰۳). Introduction to graph theory. Prentice-Hall-India.

پیوند به بیرون

• Weisstein, Eric W. "Kneser Graph". MathWorld.
• Weisstein, Eric W. "Odd Graph". MathWorld.