主题
Search

区分数

DOWNLOAD Mathematica Notebook下载 Wolfram 笔记本

图 G 的（顶点）的标记 phi，使用集合 {1,2,...,r} 中的正整数，被称为是 r-可区分的，如果 图自同构 G 不保留所有的顶点标签。形式上，phi 是 r-可区分的，如果对于每个非平凡的 sigma in Aut(G)，都存在 x in V(G) 使得 phi(x)!=phi(xsigma)，其中 V(G) 是 G 的顶点集，Aut(G) 是 G 的 自同构群。图 G 的区分数 D(G) 然后是最小的 r，使得 G 有一个 r-可区分的标记 (Albertson and Collins 1996)。

具有相同自同构群的不同图可能具有不同的区分数。

D(G)=1 当且仅当 G 是 恒等图 时成立。图 G 及其 图补 G^_ 具有相同的区分数。

具有 |Aut(G)|<=k! 的图 G 的区分数 D(G)<=k (Tymoczko 2005; 归功于 Albertson, Collins, 和 Kleitman)。

特殊情况总结在下表中。

GD(G)
完全二部图 K_(n,n)n+1
完全图 K_nn
圈图 C_n{3 for n=3,4,5; 2 for n>=6
广义 Petersen 图 GP(n,k){3 for (n,k)=(4,1),(5,2); 2 otherwise
超立方体图 Q_n{1 for n=0; 2 for n=1; 3 for n=2,3; 2 for n>=4
路径图 P_n{1 for n=1; 2 for n>=2
星图 S_n{n for n=1,2; n-1 otherwise
n-三角图 L(K_n){1 for n=1,2; 3 for n=3,4,5; 2 for n>=6
轮图 W_n{4 for n=4; 3 for n=5,6; 2 for n>=7

另请参阅

色数, 色多项式

使用 Wolfram|Alpha 探索

参考文献

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. 自行车是怎么走的？以及其他有趣的数学谜题。 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

请引用本文为

Weisstein, Eric W. "区分数。" 来自 MathWorld--一个 Wolfram Web 资源。 https://mathworld.net.cn/DistinguishingNumber.html

学科分类