مقایسهای چندجملهای احاطهگر و احاطهگر مستقل گرافها
کلیدي ټکي:
تحلیل مقایسهای،چندجملهی احاطهگر, چندجملهی احاطهگر مستقل, مجموعه احاطهگر, مجموعه احاطهگر مستقل, نظریهی گرافچکیده
در این مقاله، مقایسهی دو چندجملهای مهم در نظریهی گراف، یعنی چندجملهای احاطهگر و چندجملهای احاطهگر مستقل ، بررسی و تحلیل میشود. نخست نشان داده میشود که برای هر گراف سادهی و هر عدد صحیح ، ضریب متناظر در چندجملهای احاطهگر مستقل همواره کوچکتر یا مساوی ضریب متناظر در چندجملهای احاطهگر است؛ یعنی . شرط لازم و کافی برای برقراری تساوی نیز ارائه میشود که براساس آن، این تساوی دقیقاً زمانی برقرار است که هر مجموعهی احاطهگر -عضوی گراف، مستقل باشد. در ادامه، رفتار ضرایب این دو چندجملهای و اختلاف آنها برای ردههای کلاسیک گرافها از جمله گراف مسیر، دور، کامل و ستاره بهطور دقیق تحلیل میشود. نتایج بهدستآمده نشان میدهد که قید استقلال نقش اساسی در کاهش تعداد مجموعههای احاطهگر دارد و اختلاف ضرایب دو چندجملهای بهشدت به ساختار گراف وابسته است. این مطالعه چارچوبی تحلیلی برای مقایسهی چندجملهایهای احاطهگر و تعمیمهای مبتنی بر قیدهای ساختاری ارائه میدهد.
Downloads
