دوره 6، شماره 1 - ( بهار 1399 )
دوره 6 شماره 1 صفحات 118-109 |
برگشت به فهرست نسخه ها
Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
Alikhani S, Soltani S. The Relationship Between the Distinguishing Number and the Distinguishing Index with the Detection Number. mmr 2020; 6 (1) :109-118
URL: http://mmr.khu.ac.ir/article-1-2625-fa.html
URL: http://mmr.khu.ac.ir/article-1-2625-fa.html
علیخانی سعید، سلطانی سمانه. رابطۀ بین عدد و شاخص متمایزکننده با عدد قابل شناسایی یک گراف. پژوهش های ریاضی. 1399; 6 (1) :109-118
سعید علیخانی*1 
، سمانه سلطانی2
، سمانه سلطانی2
1- دانشگاه یزد، دانشکدۀ ریاضی ، alikhani@yazd.ac.ir
2- دانشگاه یزد، دانشکدۀ ریاضی
2- دانشگاه یزد، دانشکدۀ ریاضی
چکیده: (4071 مشاهده)
عدد متمایز کننده 
، گراف 
عبارت است از کوچک‌ترین عدد صحیح 
به‌طوری‌که گراف دارای رنگ‌آمیزی رأسی با رنگ است که تنها تحت خودریختی همانی حفظ می‌شود. به‌صورت مشابه، شاخص متمایزکننده 
از گراف G، کوچک‌ترین عدد صحیح است که برای آن گراف دارای یک رنگ‌آمیزی یالی با d رنگ باشد که تنها تحت خودریختی همانی حفظ می‌شود. فرض کنیم گراف همبند از مرتبۀ 
و 
یک رنگ‌آمیزی از یال‌های است (ممکن است یال‌های مجاور، رنگ‌های یک‌سانی داشته باشند). برای هر رأس v از ، کد رنگی v با توجه به رنگ‌آمیزی c،k-تایی مرتب 
است که در آن 
تعداد یال‌های به رنگ i، 
، واقع بر v است. رنگ‌آمیزی c قابل شناسایی است اگر رئوس مختلف، کدهای رنگی متفاوتی داشته باشند. عدد شناسایی 
گراف ، کوچک‌ترین عدد صحیح و مثبت k است که برای آن گراف یک رنگ‌آمیزی قابل شناسایی با k رنگ داشته باشد. در این مقاله، رابطۀ بین عدد و شاخص متمایزکننده با عدد شناسایی یک گراف بررسی می‌شود. به‌ویژه، نشان می‌دهیم شاخص متمایز کننده هر گراف همبند حداکثر با عدد شناسایی آن برابر است، یعنی، 
است.
، گراف عبارت است از کوچک‌ترین عدد صحیح به‌طوری‌که گراف دارای رنگ‌آمیزی رأسی با رنگ است که تنها تحت خودریختی همانی حفظ می‌شود. به‌صورت مشابه، شاخص متمایزکننده از گراف G، کوچک‌ترین عدد صحیح است که برای آن گراف دارای یک رنگ‌آمیزی یالی با d رنگ باشد که تنها تحت خودریختی همانی حفظ می‌شود. فرض کنیم گراف همبند از مرتبۀ و یک رنگ‌آمیزی از یال‌های است (ممکن است یال‌های مجاور، رنگ‌های یک‌سانی داشته باشند). برای هر رأس v از ، کد رنگی v با توجه به رنگ‌آمیزی c،k-تایی مرتب است که در آن تعداد یال‌های به رنگ i، ، واقع بر v است. رنگ‌آمیزی c قابل شناسایی است اگر رئوس مختلف، کدهای رنگی متفاوتی داشته باشند. عدد شناسایی گراف ، کوچک‌ترین عدد صحیح و مثبت k است که برای آن گراف یک رنگ‌آمیزی قابل شناسایی با k رنگ داشته باشد. در این مقاله، رابطۀ بین عدد و شاخص متمایزکننده با عدد شناسایی یک گراف بررسی می‌شود. به‌ویژه، نشان می‌دهیم شاخص متمایز کننده هر گراف همبند حداکثر با عدد شناسایی آن برابر است، یعنی، است.
نوع مطالعه: مقاله مستقل |
موضوع مقاله:
جبر
دریافت: 1396/3/3 | ویرایش نهایی: 1399/4/18 | پذیرش: 1397/6/26 | انتشار: 1398/11/5 | انتشار الکترونیک: 1398/11/5
دریافت: 1396/3/3 | ویرایش نهایی: 1399/4/18 | پذیرش: 1397/6/26 | انتشار: 1398/11/5 | انتشار الکترونیک: 1398/11/5
ارسال پیام به نویسنده مسئول
| بازنشر اطلاعات | |
 |
این مقاله تحت شرایط Creative Commons Attribution-NonCommercial 4.0 International License قابل بازنشر است. |
