رابطه بین عدد و شاخص متمایزکننده با عدد قابل شناسایی یک گرا‎ف

عدد متمایز کننده ، گراف ‎‎‎‎‎‎‎ ‎‎‏ ‎‎عبارت است از کوچک ترین عدد صحیح ‎‎‎ ‎‎ به طوری که گراف ‎‎‎‎‎ ‎‎ دارای رنگ آمیزی راسی با ‎‎‎‎‎ ‎‎ رنگ است که تنها تحت خودریختی همانی حفظ می شود. به صورت مشابه، شاخص متمایزکنند‎ه ‎ از گرا‎ف ‎‎‎G‎، کوچک ترین عدد صحیح ‎‎  است که برای آن گراف ‎‎  دارای یک رنگ آمیزی یالی با ‎‎‎d‎‎ رنگ باشد ‎‎که تنها تحت خودریختی همانی حفظ می شود. فرض کنیم ‎‎‎‎‎ ‎‎ گراف همبند از مرتبه ‎‎‎‎‎ ‎‎ و  یک رنگ آمیزی از یال ها‎ی ‎‎  است (ممکن است یال های مجاور، رنگ های یک سانی داشته باشند). برای هر را‎س ‎‎‎v‎‎ ا‎ز ‎‎، کد رنگی ‎‎v‎‎ با توجه به‎‎ رنگ آمیزی ‎‎‎‎‎c‎‎‎،k-تایی مرتب‎‎ ‎‎‎  است که در آن ‎‎‎ ‎‎ تعداد یال های به رنگ‎‎ ‎‎‎‎i‎‎، ‎ ‎‎، واقع بر ‎‎‎‎v‎‎‎ است. رنگ آمیز‎ی ‎‎‎c‎‎ قابل شناسایی است اگر ریوس مختلف، کدهای رنگی متفاوتی داشته باشند. عدد شناسایی   ‎ گراف ‎‎‎ ‎‎، کوچک ترین عدد صحیح و مثبت k‎‎ است که برای آن گرا‎ف ‎‎‎ ‎‎ یک رنگ آمیزی قابل شناسایی با‎ k‎ رنگ داشته باشد. در این مقاله، رابطه بین عدد و شاخص متمایزکننده با عدد شناسایی یک گراف بررسی می شود. به ویژه، نشان می دهیم شاخص متمایز کننده هر گراف همبند حداکثر با عدد شناسایی آن برابر است، یعنی،   است.