گراف نسر

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
این گراف با گراف پترسن ایزومورف است.

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

مثال‌ها[ویرایش]

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

خصوصیات[ویرایش]

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

منابع[ویرایش]

پیوند به بیرون[ویرایش]