گراف‌های پنجه‌آزاد

تشخیص

بررسی کردن پنجه‌آزاد بودن یا نبودن یک گراف دلخواه با  رأس و  یال در زمان  کار ساده‌ای است، کافی است به ازای هر ۴ رأس بررسی کرد که آیا زیرگراف القایی روی آن ۴ رأس تشکیل یک پنجه می‌دهد یا خیر. رویکردی پیچیده‌تر اما اندکی کارا تر این است که در گراف پنجه‌آزاد، گراف مکمل همسایه‌های هر رأس مثلث‌آزاد نباشد. یک گراف مثلث دارد اگر و تنها اگر عددی ناصفر روی قطر مربع ماتریس مجاورت آن باشد، پس یافتن مثلث در گراف از نظر پیچیدگی زمانی مانند محاسبهٔ ضرب دو ماتریس  است. از این رو، با استفاده از الگوریتم کوپراسمیت–وینوگارد زمان تشخیص پنجه آزاد بودن یک گراف  خواهد بود.
در سال ۲۰۰۰ میلادی، کلاکس، کراتش و مولر به این نتیجه رسیدند که هر رأس در گراف پنجه‌آزاد حداکثر  همسایه دارد، در غیر اینصورت طبق قضیهٔ توران همسایه‌های آن رأس به تعداد کافی یال نخواهند داشت تا بتوانند مکمل یک گراف مثلث‌آزاد باشند. با این مشاهده بررسی همسایه‌های یک رأس با استفاده از روش ضرب ماتریسی سریع تر از قبل انجام می‌شود و به زمانی نظیر ضرب دو ماتریس  نیاز دارد و برای رئوس با درجه کمتر این بررسی حتی سریع تر هم انجام می‌پذیرد.
بدترین حالت این الگوریتم زمانی رخ می‌دهد که  رأس هرکدام  همسایه داشته باشند و بقیهٔ رئوس تعداد کمتری همسایه داشته باشند. در این حالت زمان اجزای کل
 خواهد بود.

شمارش

چون مکمل هر گراف مثلث‌آزاد یک گراف پنجه‌آزاد است، رشد تعداد گراف‌های پنجه‌آزاد حداقل به اندازهٔ رشد تعداد گراف‌های مثلث‌آزاد سریع است، به صورت تابعی نمایی بر حسب . تعداد گراف‌های پنجه‌آزاد  رأسی برای   برابر است با:

(دنبالهٔ A022562 در OEIS).
اگر گراف‌های ناهمبند را هم بشماریم، تعداد باز هم بیشتر می‌شود:

(دنبالهٔ A086991 در OEIS).
با بهره بردن از تکنیک Palmer, Read & Robinson می‌توان گراف‌های مکعبی پنجه‌آزاد (گراف مکعبی، همان گراف ۳-منتظم است) را بسیار کارا شمرد که برای مسائل شمارش گراف امری طبیعی نیست.

تطابق

لاس ورناگس (۱۹۷۵) و سومنر (۱۹۷۴)‌ به‌طور مستقل اثبات کردند که هر گراف زوج رأسی همبند پنجه‌آزاد یک تطابق کامل دارد. یکی از نتایج مهم این نکته در گراف یالی آن است که در هر گراف با تعداد زوجی یال می‌توان یال‌ها را به مسیرهایی به طول ۲ افراز کرد. از تطابق کامل می‌توان برای توصیف یکی دیگر از خصوصیات گراف‌های پنجه‌آزاد استفاده کرد:
گراف‌هایی که هر زیرگراف القایی زوج رأسی همبند آن‌ها دارای تطابق کامل باشد، پنجه آزادند و برعکس.
نتیجهٔ قوی تر اثبات Sumner نشان می‌دهد که در هر گراف همبند پنجه آزاد دو رأس مجاور وجود دارند که با حذف آنها گراف همچنان همبند می‌ماند.
برای اثبات، Sumner دو رأس و  را به گونه ای یافت که بیشترین فاصلهٔ ممکن نسبت به یکدیگر را داشته باشند و از میان همسایه‌های رأس  رأس  را به گونه ای انتخاب کرد که از  دورترین باشد. آنگونه که او نشان داد، رئوس  و  در هیچ کوتاه‌ترین مسیر از هیچ رأسی از گراف نسبت به  قرار ندارند. پس حذف این دو رأس گراف را همبند نگاه می‌دارد. با تکرار همین عمل و حذف رئوس متطابق، یک تطابق کامل از گراف پنجه‌آزاد داده شده به دست می‌آید.
ایدهٔ اثبات بالا برای وقتی که  یک رأس دلخواه از گراف باشد، و  یکی از دورترین رئوس نسبت به  باشد و  هم یکی از دورترین همسایه‌های  نسبت به  باشد همچنان کاراست. در این حالت حذف دو رأس  و  فاصلهٔ بقیهٔ رئوس نسبت به  را تغییر نخواهد داد؛ بنابراین فرایند یافتن تطابق کامل در گراف با یافتن و حذف زوج  که نسبت به  دورترین رئوس هستند با پیمایش پس ترتیب درخت جستجوی اول سطحی که از رأس  ریشه دار شده باشد، در زمان خطی امکان‌پذیر است. چروباک، نائور و نویک الگوریتم دیگری بر اساس جستجوی عمق اول در زمان خطی ارائه کردند. آنها برای همین مسئله الگوریتم کارایی برای پردازش موازی نیز ارائه دادند. چند نتیجه شامل نتایج زیر بدست آوردند:
هر گراف  همبند -آزاد زوج رأسی برای هر  تطابق کامل دارد هر گراف پنجه آزاد فرد رأسی با حداکثر یک رأس درجه ۱ قابل افراز به یک دور فرد و یک تطابق است. هر گراف پنچه آزاد به ازای هر  کمتر از نصف مینیمم درجهٔ گراف، که  یا تعداد راس‌ها زوج است، گراف یک عاملِ  دارد.