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

عدد متمايز كننده D(G)، گراف G عبارت است از كوچك‌ترين عدد صحيح به‌طوري‌كه گراف d داراي رنگ‌آميزي رأسي با d رنگ است كه تنها تحت خودريختي هماني حفظ مي‌شود. به‌صورت مشابه، شاخص متمايزكننده D (G) از گراف G، كوچك‌ترين عدد صحيح d است كه براي آن گراف داراي يك رنگ‌آميزي يالي با d رنگ باشد كه تنها تحت خودريختي هماني حفظ مي‌شود. فرض كنيم G گراف همبند از مرتبۀ n≥3 و c:E(G)→{1,2,...,k} يك رنگ‌آميزي از يال‌ها ي G است (ممكن است يال‌هاي مجاور، رنگ‌هاي يك‌ساني داشته باشند). براي هر رأس v از G، كد رنگي v با توجه به رنگ‌آميزي c ،kتايي مرتب c(v)=(a1, a2, ..., ak) است كه در آن ai تعداد يال‌هاي به رنگ i ، k≥i≥1 ، واقع بر v است. رنگ‌آميزي c قابل شناسايي است اگر رئوس مختلف، كدهاي رنگي متفاوتي داشته باشند. عدد شناسايي det(G) گراف G، كوچك‌ترين عدد صحيح و مثبت k است كه براي آن گراف G يك رنگ‌آميزي قابل شناسايي با k رنگ داشته باشد. در اين مقاله، رابطۀ بين عدد و شاخص متمايزكننده با عدد شناسايي يك گراف بررسي مي‌شود. به‌ويژه، نشان مي‌دهيم شاخص متمايز كننده هر گراف همبند حداكثر با عدد شناسايي آن برابر است، يعني، det(G)≥D (G) است.