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

Abstract

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