Distinguishing Number

A labeling  of (the vertices) of a graph  with positive integers taken from the set {1,2,...,r}" src="https://mathworld.wolfram.com/images/equations/DistinguishingNumber/Inline3.svg" style="height:22px; width:91px" /> is said to be -distinguishing if no graph automorphism of  preserves all of the vertex labels. Formally,  is -distinguishing if for every nontrivial , there exists  such that , where  is the vertex set of  and  is the automorphism group of . The distinguishing number of  of  is then the smallest  such that  has a labeling that is -distinguishing (Albertson and Collins 1996).

Different graphs with the same automorphism group may have different distinguishing numbers.

 iff  is an identity graph. The distinguishing number of a graph  and its graph complement  are the same.

A graph  with  has distinguishing number  (Tymoczko 2005; due to Albertson, Collins, and Kleitman).

Special cases are summarized in the following table.

complete bipartite graph
complete graph
cycle graph	{3 for n=3,4,5; 2 for n>=6" src="https://mathworld.wolfram.com/images/equations/DistinguishingNumber/Inline34.svg" style="height:68px; width:198px" />
generalized Petersen graph	{3 for (n,k)=(4,1),(5,2); 2 otherwise" src="https://mathworld.wolfram.com/images/equations/DistinguishingNumber/Inline36.svg" style="height:68px; width:344px" />
hypercube graph	{1 for n=0; 2 for n=1; 3 for n=2,3; 2 for n>=4" src="https://mathworld.wolfram.com/images/equations/DistinguishingNumber/Inline38.svg" style="height:140px; width:164px" />
path graph	{1 for n=1; 2 for n>=2" src="https://mathworld.wolfram.com/images/equations/DistinguishingNumber/Inline40.svg" style="height:68px; width:130px" />
star graph	{n for n=1,2; n-1 otherwise" src="https://mathworld.wolfram.com/images/equations/DistinguishingNumber/Inline42.svg" style="height:68px; width:200px" />
-triangular graph	{1 for n=1,2; 3 for n=3,4,5; 2 for n>=6" src="https://mathworld.wolfram.com/images/equations/DistinguishingNumber/Inline45.svg" style="height:104px; width:198px" />
wheel graph	{4 for n=4; 3 for n=5,6; 2 for n>=7" src="https://mathworld.wolfram.com/images/equations/DistinguishingNumber/Inline47.svg" style="height:104px; width:164px" />

---

REFERENCES

Albertson, M. and Collins, K. "Symmetry Breaking in Graphs." Electronic J. Combinatorics 3, No. 1, R18, 17 pp., 1996.

 http://www.combinatorics.org/ojs/index.php/eljc/article/view/v3i1r18.Konhauser, J. D. E.; Velleman, D.; and Wagon, S. Which Way Did the Bicycle Go? And Other Intriguing Mathematical Mysteries. Washington, DC: Math. Assoc. Amer., 1996.Rubin, F. Problem 729. In J. Recr. Math. 11, 128, 1979.

(Solution in Vol. 12, 1980).Tymoczko, J. "Distinguishing Numbers for Graphs and Groups." 17 Mar 2005. http://arxiv.org/abs/math/0406542

اخر الاخبار

اخبار العتبة العباسية المقدسة

العتبة العباسية المقدسة تواصل تنظيم مجالس العزاء الصباحية بذكرى زيارة عاشوراء

مواكب العزاء تستذكر في التاسع من شهر المحرم شهادة عبدالله الرضيع بن الحسين (عليهما السلام)

العتبة العباسية المقدسة تستذكر تضحيات القاسم بن الحسن (عليهما السلام)

شعبة الحرم الشريف تواصل تنفيذ خطتها الخاصة بشهر المحرّم داخل مرقد أبي الفضل العباس (عليه السلام)

المزيد

الآخبار الصحية

لهذا السبب.. إغلاق 25 مركزًا لعلاج الإدمان في مصر ؟

خلافا للاعتقاد الشائع.. علماء يكشفون أسرار بذور البطيخ ؟!

هذا ما يحدث لجسمك عند تناولك الطماطم بانتظام !

تعرف على أطعمة تسرّع "تعافي الجسم" من حروق الشمس

المزيد

الآخبار التكنلوجية

الثلوج تغطي الصحراء الأكثر جفافا في العالم!

بتلسكوب "ألما".. التقاط صورا غير مسبوقة لبدايات الكون !

هل هاتفك مراقب؟.. 5 علامات خطيرة تكشف التجسس عليك

دبي تطلق أول رحلة تجريبية للتاكسي الجوي

المزيد

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength