ثابت کنید که اگر $m$ به پیمانهٔ ۴ همنهشت با ۰ یا ۱ باشد، آنگاه گراف دوری با درازای $m$ یک گراف دلپذیر است.

Question

ثابت کنید اگر $4 \mid m$ یا $4 \mid m+1$ آنگاه گراف $C_{m}$ دلپذیر است.

ویرایشگر: پرسش‌کننده متن بیشتری وارد نکرده‌است.

Answer 1

پرسش شما مطلب مشهوری در این زمینه است. احتمال می‌دهم نام الکساندر رُسا به گوش‌تان خورده باشد. در مقالهٔ معروفش به نام On certain valuations of the vertices of a graph که در ResearchGate به صورت Open access نیز موجود است در قضیهٔ یک مطلب شما را ثابت می‌کنند. دور به درازای $n$ در آن مقاله $n$-ضلعی گفته‌شده‌است و آنچه شما دلپذیر بودن (برچسب‌گذاری دلپذیر) می‌نامید در آن مقاله ارزیابیِ $\beta$، valuation-$\beta$ نامیده‌شده‌است و توجه کنید که ارزیابِ $\alpha$، ارزیابِ $\beta$ نیز است. بعلاوه با توجه به لم یک آن مقاله حکم پرسش شما اگر و تنها اگر می‌شود.

پیوند مقاله در سایت ResearchGate.