文 献 综 述
摘要 图中的识别码是图的一个支配集，并且它与图中每个顶点的闭领域的交集互异。图G中识别码的最小基数称为G的识别码数，并记为gamma;（G)。图G和图H的笛卡尔积，记为GH，是顶点集为V(G)times;V(H)的图，图GH中的两个顶点（u，u）和（v，v)是相邻的，若uvE(G) 且u= v, 或者u= v且 uvE(H)。当H=K时，G□K称为G的棱柱。
关键词 识别码 支配集 笛卡尔积 棱柱
图中的识别码是图的一个支配集，并且它与图中每个顶点的闭领域的交集互异。图G中识别码的最小基数称为G的识别码数，并记为gamma;（G)，显然，任意存在两个顶点具有相同闭邻域的图都没有识别码。识别码最先是由Karpovsky、Chakrabarty和Levitin于1998年提出的[1，2]，他们使用识别码来分析多元处理器系统中的故障检测问题。故障检测的目的是对系统进行测试和定位故障处理器，多元处理器系统可以建模为一个无向图G=（V，E），其中V是处理器的集合，E是系统的链接集，在选定的处理器上执行特定的软件程序来进行检测。这些处理器的选择是通过生成允许唯一识别错误处理器的码C来完成的，每个对应于码字顶点的处理器都会测试自身和所有与它相邻的处理器，这对应于使用以码字为中心的半径为1的球。因此，最优码(最小码字数)能将实现故障诊断所需的开销降到最低。自1998年以来，识别码在许多类图中都进行了研究，在Antoine Lobstein的网页上可以找到关于识别码的详细的优秀参考列表[3]。图G和图H的笛卡尔积，记为GH，是顶点集为V(G)times;V(H)的图。图GH中的两个顶点（u，u）和（v，v)是相邻的，若uvE(G) 且u= v, 或u= v且 uvE(H)。当H为完全图K时，G□K称为G的棱柱。
笛卡尔积的识别码在超立方体,有限和无限格,团的直积和笛卡尔积以及树，路径，圈中都有着广泛的应用。在[4]和[5]中给出了笛卡尔积图的结构和它们的子图的性质，设计了识别积图及其子图的有效算法，并探讨了积图及其子图(汉明图、超立方体、棱柱和其他类图)之间的关系，以及包括从编码理论，频率分配，和计算化学等各个方面的应用。在[6,7,8]中给出了超立方体和汉明图的识别码的拓扑性质，n维超立方体Q=Q□K，Q=K，是一种基于二元n维拓扑的高度并发松耦合多元处理器，基于超立方体拓扑的处理器因其强大的互连特性而被认为是理想的并行结构，而二元汉明空间，即二元超立方体。接着先给出格的定义：设〈L，le;〉是一个偏序集合，如果L中每一对元素a，b都有最大下界和最小下界，则称此〈L，le;〉为格。设V为图的顶点集，d（c，v）表示从c到v的最短路径的边的数目，如果集合{cC|d（c，v）le;r，vF}对于所有最多k个顶点的子集FV都是不同的，则称V的子集C为一个（r，le;k）-识别码。[9]中证明了（1，le;2）-识别码的密度的一个新下界为5/12，并且在无穷王格中构建了一个密度为2/7的（2，le;2）-识别码。[10]中证明了在无穷正方形格中，任意（r，le;2）-识别码的密度至少为1/8，且存在一个（r，le;2）-识别码的序列C使得当r→infin;时，C的密度→1/8；给出了在无穷三角形格中（r，le;2）-识别码的一个序列C满足当r→infin;时，C的密度→0。[11]中证明了在无穷六边形格中所有识别码的密度至少为16/39，且存在密度为3/7的识别码。
对于任意图G，G的团是G的一个完全子图，即每对顶点之间都存在边的顶点集，而完全图是每对顶点之间恰有一条边的图，因此，所有完全图都是它自身的团。[12,13]证明了几个路径与完全图的笛卡尔积的一般性下界，并且给出了当完全图K的阶数为三或至少为五，路径P阶数至少为三时它们的笛卡尔积K□P的识别码的最小基数。[14]中作者确定了两个相同大小的团的笛卡尔积K□K的识别码的最小基数（gamma;（K□K）=），并且证明了当nge;5且为奇数时该识别码在行列的排列上是唯一的，给出了当nge;4且为偶数时的两种最小识别码。给定两个图G=(V，E)和G=(V，E)，G和G的直积，记作Gtimes;G，其点集为笛卡尔积Vtimes;V，边集E(Gtimes;G)={(u，u）(v，v）|uvE且uvE}。[15]中给出了特定条件下两个团的直积的识别码（记为C=gamma;（Ktimes;K），n,mge;2）的精确值，以及C的最小基数的可达上下界。
参考文献
[1] M.G.Karpovsky, K.Chakrabarty, L.B. Levitin,: On a new class of codes for identifying vertices in graphs. IEEE Trans. Inf. Theory 44(2), 599–611 (1998)
[2] M.G.Karpovsky, K.Chakrabart, L.B.Levitiin, D.R.Avresky,: On the covering of vertices for fault diagnosis in hypercubes. Inform. Process. Lett. 69(2), 99–103 (1999)
