تسجيل الدخول

تسجيل

Distinguishing Number

المؤلف:  Albertson, M. and Collins, K.

المصدر:  "Symmetry Breaking in Graphs." Electronic J. Combinatorics 3, No. 1, R18

الجزء والصفحة:  ...

26-3-2022

2493

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