بررسی همیلتونی بودن گراف های ۲‐همبند فاقد سه تایی های خاص به عنوان زیرگراف القایی

در این مقاله، شرایط کافی برای همیلتونی بودن گراف های ۲‐همبند بررسی شده است. به طور خاص، نشانبا مرتبه ای به اندازه ی کافی بزرگ فاقد برخی زیرگراف های القایی مشخصباشد، G داده شده است که اگر یک گرافهمیلتونی خواهد بود. همیلتونی بودن گراف ها یکی از مسائل چالش برانگیز در نظریه گراف است که تشخیصآن برایگراف های دلخواه، در حالت کلی دشوار و از نظر محاسباتی پیچیده است. از این رو، پژوهش بر روی گراف هایی که فاقدساختارهای خاص هستند، می تواند ابزار مناسبی برای یافتن شرایط کافی جهت تضمین وجود دور همیلتونی باشد. نتایجرا شامل نشود، همیلتونی Z و ۱ P۵ ،K اصلی تحقیق بیان می کنند که هر گراف ۲‐همبند که زیرگراف های القایی ۱,۴باشد، J۲(m) و P۴ ،K یا نیز ۱,۴ B و ۲ P۴ ،K است. همچنین، اگر یکگراف ۲‐همبند فاقد زیرگراف های القایی ۱,۴خاصیت همیلتونی را خواهد داشت. اثبات این نتایج مبتنی بر برهان خلف و تحلیل دقیق زیرگراف های القایی در ساختارگراف است.

کلیدواژه ها:

گراف همیلتونی ، R-آزاد ، زیرگراف القایی ، دور همیلتونی