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

اخر الاخبار

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

سماحة السيد الصافي يكرم عددًا من عوائل الشهداء ضمن فعاليات مهرجان روح النبوة النسوي العالمي الثامن

إحدى أمهات الشهداء: نعتز بتضحيات أبنائنا ونفتخر بشهادتهم دفاعًا عن الدين والمقدسات

ضمن فعاليات مهرجان روح النبوة… عرض فيلم يوثق نشاطات الشعب النسوية في العتبة العباسية المقدسة

فعاليات مهرجان روح النبوة الثقافي تشهد تقديم أوبريت الثقلين القرآني

المزيد

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

ماذا يحدث لجسمك عند تناول الوجبات السريعة يوميا؟

لصحة عظام المرأة.. الشاي أفضل أم القهوة؟

لبناء العضلات وإنقاص الوزن.. ما أفضل توقيت لتناول البيض؟

أطعمة صحية تساعد على التعافي من "الإنفلونزا الخارقة"

المزيد

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

دراسة تكشف قدرة الحيتان على سماع الأصوات منخفضة وعالية التردد من مسافة بعيدة

تجربة جديدة: الأسفلت المدعوم بالطحالب يقاوم الحفر ويقلل الانبعاثات الكربونية

تسريبات تكشف ملامح أول هاتف قابل للطي من "أبل"

رصد نوع نادر من القطط في تايلاند للمرة الأولى منذ عقود

المزيد

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

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