روابطی بین عدد تشخیص و پارامترهای دیگر گراف ها

یک رنگ آمیزی تشخیص از گرافی ساده مانند G، عبارت است از یک رنگ آمیزی رئوس G به طوری که تنها خودریختی ای از G که این رنگ آمیزی را حفظ می کند، خودریختی همانی باشد. به عبارت دیگر، این رنگ آمیزی همه ی تقارن های G را «می شکند». عدد تشخیص یک گراف مانند G، که با D(G)نمایش داده می شود، کوچک ترین تعداد رنگ مورد نیاز برای یک رنگ آمیزی تشخیص~G است. در این مقاله، علاوه بر مطالعه ی برخی از روابط موجود بین D(G) و پارامترهای مهم گرافی، مفهوم (D,\alpha)-عادی بودن یک گراف را تعریف می کنیم که بیانگر مقایسه ی بین D(G) و عدد استقلال \alpha(G) است. سپس طیف وسیعی از گراف ها را از دیدگاه (D,\alpha)-عادی بودن مطالعه و رده بندی هایی را برای گراف های دوبخشی، چندبخشی کامل، گراف های جانسون تعمیم یافته و حاصل ضرب های دکارتی و گراف های خط برخی از گراف ها ارائه می کنیم.

روابطی بین عدد تشخیص و پارامترهای دیگر گراف ها Keywords:

گراف , عدد تشخیص , عدد تثبیت کننده , گراف خط , گراف چندبخشی