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