گراف خودمکمل

گراف خود مکمل گرافی است که با مکمل خود یک‌ریخت است. دوتا از ساده‌ترین گراف‌های خود مکمل یک گراف مسیری با ۴ راس و گراف دوری با ۵ راس است.

یک گراف خود مکمل، گراف N شکل به رنگ آبی با مکمل آن که Z شکل و به رنگ قرمز هاشور دار است، یک ریخت است.

مثال‌ها

هر گراف ایده‌آلی یک گراف خود مکمل است. به‌طور مثال گراف ایده‌آل با ۹ راس نام لاتین ۳×3 rook's graph یک گراف خودمکمل است زیرا دارای یک تقارن است که راسی را در مرکز گراف ثابت نگه می‌دارد و مکان ۴ راس کناری نزدیک مرکز را با ۴ راس گوشه‌ای شبکه عوض می‌کند. همهٔ گراف‌های خودمکمل که به شدت منظم هستند با تعداد راس کمتر از ۳۷ یک گراف ایده‌آل هستند؛ گراف‌های ب شدت منظم با تعداد گره ۳۷ و ۴۱ و ۴۹ نیز وجود دارد که نیستند. گراف رادو هم یک گراف خودمکمل نامتناهی است.

ویژگی‌ها

هرگراف خود مکمل همبند است. یک گراف خود مکمل با n راس دقیقاً به اندازهٔ نصف تعداد یال‌های گراف کامل یال دارد به عبارت دیگر 4/(n(n-۱ و به شرط اینکه تعداد گره بیشتر از ۱ باشد حتماً دارای یک قطر به اندازه ۲ یا ۳ است. چون (n(n-1 باید بر ۴ بخش پذیر باشد پس n به پیمانه ۴ باید با ۰ یا ۱ هم ارز باشد؛ ب طور مثال یک گراف کامل ۶راسه نمی‌تواند یک گراف خود مکمل باشد.

هر گراف خود مکمل زوج راسی دارای حداقل یک تطابق کامل است.

هر گراف خود مکمل فرد راسی یک راس دارد که با حذف آن گراف باقیمانده همچنان خود مکمل باشد.

پیچیدگی محاسباتی

مشکل تشخیص همریخت بودن دو گراف و تشخیص خودمکمل بودن یک گراف همان مسئله عمومی همریختی گراف است.