Distinguishing Number
المؤلف:
Albertson, M. and Collins, K.
المصدر:
"Symmetry Breaking in Graphs." Electronic J. Combinatorics 3, No. 1, R18
الجزء والصفحة:
...
26-3-2022
2085
Distinguishing Number
A labeling 
of (the vertices) of a graph 
with positive integers taken from the set ![<span style=]()
{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  |
![<span style=]() {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  |
![<span style=]() {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  |
![<span style=]() {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  |
![<span style=]() {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  |
![<span style=]() {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  |
![<span style=]() {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  |
![<span style=]() {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
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
