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

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

relations between the distinguishing number and some other graph parameters

a distinguishing coloring of a simple graph g is a vertex coloring of g which is preserved only by the identity automorphism of g. in other words, this coloring ``breaks’’ all symmetries of g. the distinguishing number d(g) of a graph g is defined to be the smallest number of colors in a distinguishing coloring of g. this concept of “symmetry breaking” was first proposed by babai in 1977 and after the publication of a seminal paper by albertson in 1996, it attracted the attention of many mathematicians. in this paper, along with studying some relations between d(g) and some other important graph parameters, we introduce the concept of a (d,alpha)-ordinary graph which displays the comparison between d(g) and the independence number alpha(g). then we consider the classification of (d,alpha)-ordinary graphs in various families of graphs such as forests, cycles, generalized johnson graphs, cartesian products of graphs and line graphs of connected claw-free graphs. we also propose some conjectures and discuss about some future research directions in this topic.