The distinguishing number of the augmented cube and hypercube powers

详细信息	查看全文 | 推荐本文 |

• 作者：Melody Chan
• 关键词：Distinguishing number ; Symmetry breaking ; Hypercube ; Augmented cube
• 刊名：Discrete Mathematics
• 出版年：2008
• 期刊代码：47_0012365x
• 类别：cp
• 出版时间：6 June 2008
• 卷：308
• 期：11
• 页码：2330-2336
• 文件大小：159 K

摘要

The distinguishing number of a graph decoration:none; color:black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6V00-4NSX05S-2&_mathId=mml2&_user=1067359&_cdi=5632&_rdoc=34&_acct=C000050221&_version=1&_userid=10&md5=7596d6afe39eeca6b43c06dbcf1a3dcb" title="Click to view the MathML source" alt="Click to view the MathML source">G, denoted decoration:none; color:black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6V00-4NSX05S-2&_mathId=mml3&_user=1067359&_cdi=5632&_rdoc=34&_acct=C000050221&_version=1&_userid=10&md5=9bf56c346339322c98db6dc1d9510de6" title="Click to view the MathML source" alt="Click to view the MathML source">D(G), is the minimum number of colors such that there exists a coloring of the vertices of decoration:none; color:black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6V00-4NSX05S-2&_mathId=mml4&_user=1067359&_cdi=5632&_rdoc=34&_acct=C000050221&_version=1&_userid=10&md5=d9abc8ccb7aff745a450809865746057" title="Click to view the MathML source" alt="Click to view the MathML source">G where no nontrivial graph automorphism is color-preserving. In this paper, we answer an open question posed in Bogstad and Cowen [The distinguishing number of the hypercube, Discrete Math. 283 (2004) 29–35] by showing that the distinguishing number of d=retrieve&_udi=B6V00-4NSX05S-2&_mathId=mml5&_user=1067359&_cdi=5632&_rdoc=34&_acct=C000050221&_version=1&_userid=10&md5=3751751115fa58bfc10af09204c2b58a">direct.com/cache/MiamiImageURL/B6V00-4NSX05S-2-HX/0?wchp=dGLzVlz-zSkzV" alt="View the MathML source" title="View the MathML source" align="absbottom" border="0" height=19 width="21"/>, the decoration:none; color:black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6V00-4NSX05S-2&_mathId=mml6&_user=1067359&_cdi=5632&_rdoc=34&_acct=C000050221&_version=1&_userid=10&md5=826742cde43af76e1e1e22dd720446a1" title="Click to view the MathML source" alt="Click to view the MathML source">pth graph power of the decoration:none; color:black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6V00-4NSX05S-2&_mathId=mml7&_user=1067359&_cdi=5632&_rdoc=34&_acct=C000050221&_version=1&_userid=10&md5=3d9d55f084f4be5c934cf0a9a5613a0a" title="Click to view the MathML source" alt="Click to view the MathML source">n-dimensional hypercube, is 2 whenever decoration:none; color:black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6V00-4NSX05S-2&_mathId=mml8&_user=1067359&_cdi=5632&_rdoc=34&_acct=C000050221&_version=1&_userid=10&md5=ddfe8da856190d84ef74767370c3c7d8" title="Click to view the MathML source" alt="Click to view the MathML source">2<p<n-1. This completes the study of the distinguishing number of hypercube powers. We also compute the distinguishing number of the augmented cube decoration:none; color:black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6V00-4NSX05S-2&_mathId=mml9&_user=1067359&_cdi=5632&_rdoc=34&_acct=C000050221&_version=1&_userid=10&md5=f5f02f5dac8f9bcab10ea915a804bff4" title="Click to view the MathML source" alt="Click to view the MathML source">AQ_n, a variant of the hypercube introduced in Choudum and Sunitha [Augmented cubes, Networks 40 (2002) 71–84]. We show that decoration:none; color:black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6V00-4NSX05S-2&_mathId=mml10&_user=1067359&_cdi=5632&_rdoc=34&_acct=C000050221&_version=1&_userid=10&md5=deeee629cc68cbe23e00c70dad1502d1" title="Click to view the MathML source" alt="Click to view the MathML source">D(AQ₁)=2; decoration:none; color:black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6V00-4NSX05S-2&_mathId=mml11&_user=1067359&_cdi=5632&_rdoc=34&_acct=C000050221&_version=1&_userid=10&md5=4ae6605bcf57c548dba324ffb00529f8" title="Click to view the MathML source" alt="Click to view the MathML source">D(AQ₂)=4; decoration:none; color:black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6V00-4NSX05S-2&_mathId=mml12&_user=1067359&_cdi=5632&_rdoc=34&_acct=C000050221&_version=1&_userid=10&md5=6e0ca1199df77ec3c2c1f4551c30e476" title="Click to view the MathML source" alt="Click to view the MathML source">D(AQ₃)=3; and decoration:none; color:black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6V00-4NSX05S-2&_mathId=mml13&_user=1067359&_cdi=5632&_rdoc=34&_acct=C000050221&_version=1&_userid=10&md5=dac2dc24935c8146d26495563717e4ce" title="Click to view the MathML source" alt="Click to view the MathML source">D(AQ_n)=2 for decoration:none; color:black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6V00-4NSX05S-2&_mathId=mml14&_user=1067359&_cdi=5632&_rdoc=34&_acct=C000050221&_version=1&_userid=10&md5=dbad69ec0bc5d5ffdd70090c95043f90" title="Click to view the MathML source" alt="Click to view the MathML source">ndirect.com/scidirimg/entities/2a7e.gif" alt="greater-or-equal, slanted" title="greater-or-equal, slanted" border="0">4. The sequence of distinguishing numbers d=retrieve&_udi=B6V00-4NSX05S-2&_mathId=mml15&_user=1067359&_cdi=5632&_rdoc=34&_acct=C000050221&_version=1&_userid=10&md5=309debdb8962ef83ddf3bb3af5e43f50">direct.com/cache/MiamiImageURL/B6V00-4NSX05S-2-24/0?wchp=dGLzVlz-zSkzV" alt="View the MathML source" title="View the MathML source" align="absbottom" border="0" height=20 width="100"/> answers a question raised in Albertson and Collins [An introduction to symmetry breaking in graphs, Graph Theory Notes N.Y. 30 (1996) 6–7].