双凯莱图的完全完备码.pdf

书书书第 卷第 期烟台大学学报（自然科学与工程版）年 月 （）文章编号：（）：收稿日期：基金项目：山东省自然科学基金资助项目（）。通信作者：王燕（），教授，博士，主要研究方向为拓扑图论。双凯莱图的完全完备码李建勋，王燕（烟台大学数学与信息科学学院，山东 烟台 ）摘要：给出了正则双凯莱图存在完全完备码的若干充分必要条件，并给出了群的子群在其双凯莱图中可以作为完全完备码的充分必要条件。关键词：双凯莱图；完全完备码；覆盖中图分类号：文献标志码：完备码（图论中也称为有效控制集）问题是基于图中顶点集合划分提出的，目的是利用图中的孤立点集将所有顶点进行划分。这种划分也是图模拟网络进行稳定性研究的一个重要方面。而完全完备码是利用图中的匹配来代替孤立点集来划分图的顶点集合，这样也增加了网络的稳定性。定义 假定 是一个图，是顶点集 （）的一个子集。若 的每一个点都与 中的唯一的一个点相邻，则称 是 的一个完全完备码。由定义可知，中每一个点也恰好和它内部的一个点相邻，因而 是一个匹配。近些年来，点传递图尤其是凯莱图中的完全完备码问题受到了广泛关注。例如文献 刻画了二部凯莱图的完全完备码，并给出了某些循环 图存在完全完备码的充要条件。文献 给出了有限群的一个共轭封闭子集构成该群的凯莱图的完全完备码的充要条件。文献 给出了完备码个数为 的方幂的循环图存在完全完备码的充要条件以及给出了子群可作为完全完备码的一个充要条件。文献 刻画了奇素数度循环图中存在完全完备码的充要条件。文献 讨论了循环群上 度凯莱图的完全完备码问题。关于交换群上的凯莱图，文献 给出了交换群上 度凯莱图存在完全完备码的充要条件。本研究关注双凯莱图完全完备码的存在性问题。一般来说，双凯莱图不是点传递图，但是它是最接近点传递图的一类图。定义 设 是一个有限群，是 的子集合，满足 ，。定义 关于，的双凯莱图，记作 （；，）。其中 的点集合 （），边集合 （），（），（），（），。特别地，如果 ，则称 是一个 图，关于 图，可以参考文献 。任取 ，令（），或 ，则 为图的一个自同构。令 ，则 为图 的一个自同构群且在其顶点集合上作用恰好有两个轨道，分别为 和。虽然双凯莱图非常接近点传递图，但双凯莱图的完备码与完全完备码的研究还很少。文献 研究了 ，时双凯莱图存在完备码的充要条件。在图论中，每个顶点度数相同的图被称为正则图。本文主要研究正则双凯莱图的完全完备码问题。第 节，列出了双凯莱图及完全完备码的一些基本性质。第 节给出了正则双凯莱图的一个顶点子集合是完全完备码的几个等价条件。作为第 节主要结果的应用，第 节考虑了一些特殊的完全完第 期李建勋，等：双凯莱图的完全完备码备码。预备知识从定义可以比较容易推出连通双凯莱图的以下基本性质。引理 设 是一个有限群，是 的子集合，满足 ，（；，）是 的一个双凯莱图。如果 连通，则以下结论成立：（）由 生成。（）在同构的意义下可以假定 中包含 的单位元。（）对任意的 （），（；，）（；，）。（）（；，）（；，）。在有限群 中，任取 的两个子集 和 ，若 与 都非空，则令 ，否则 。特别地，如果 或 ，则记 和 。显然，。设 （；，），是 上一个既单且满的映射满足（）且 。任取 （），则 ，其中 和 是 的子集。令 ，称 是 的共轭集。对任意的 ，令 （）（）；当 时，令（）（），否则令 （）（）。如果 ，令 和 。对于任意 ，（）和（）分别表示 与 在 中的邻点集合，则有（）（），（），（）（），（），。显然，（），（）。由此，对任意的 ，是图 （；，）的自同构，且对任意的，将 映到（），因此，（）（），（）（）（）定义 假定 （；，）是一个连通双凯莱图，是 到自身的一个既单且满的映射且满足（），令 （），如果对任意的 ，任意的 ，有 （），则称 是一个?拟正规子集。由定义可以直接得到命题 和命题 ，省略证明。命题 假定 （；，）是一个正则的双凯莱图，（），是 到自身的一个既单且满的映射且（），。则 是一个?拟正规子集当且仅当对任意 ，对任意的 ，且当 ，当 ，命题 是一个图，有下面三个结论成立。（）如果 是 的完全完备码，则 （）的 个子集，（），是 （）的一个划分。（），是 的两个无公共点的完全完备码，则 ，且 在 中的诱导子图是一系列无交偶圈的并。（）是 的完全完备码，对任意的 （），（）也是 的完全完备码。双凯莱图的完全完备码定理 揭示了正则双凯莱图的完全完备码与图的点划分的密切联系。定理 假定 是有限群，（；，）是 的一个正则双凯莱图。令 （），与 是 的子集。则对任意的一个 到自身的既单且满的映射 ，满足（）且 ，下述结论（）和结论（）等价。此外，若 （），那么结论（）也与结论（）、（）等价。（）是 的完全完备码。（）（）的 个子集，是 （）的一个划分，其中 ，。（），（）（）。证明注意到（），。（）（）：假定 是 的一个完全完备码，则 是一个匹配。根据命题，（）的 个子集（），（），是（）的一个划分。因为（）（），（），（）（），（），这表明 （）的 个子集，是 （）的一个划分，其中 ，。（）（）：假定 （）的 个子集，是 （）的一个划分，其中 ，则 （）（）。而且对任意的 （），存在唯一的 ，唯一的，使得 （）或（）；或存在唯一的 ，唯一的，使得（）或（），因此 （）。故 是 的完全完备码。烟台大学学报（自然科学与工程版）第 卷（）（）：由结论（）可知 显然成立。假定存在 （），即存在不同的两个元素 ，珓 使得 （珓），因此 （珓）或 （珓），即 珓 或 珓，这与 珓 矛盾。同理可证明（）与 。（）（）：由 ，可以推出 ，其中 ，。若存在不同的两个元素 ，珓 ，使得 珓 ，则 （）（珓）或 （）（珓），进而存在，珟，使得 （）（珓 珟）；或存在，珘，使得（）（珓珘）。因此 珓 或者（珓），这与（）相矛盾，因此 珓 。同理可证 珓，其中 ，珓 是 的任意两个不同的元素。又因为 ，可得 （）（）（）。所以 （）的 个子集，是 （）的一个划分，其中 ，。注 在引理 中虽然可以根据图同构来假设 ，但是该条件的存在与否会使得 （）的子集有非常大的差异。在 定 理 的 结 论（）中，若 ，则 是 这 些 个子集中的一个。反之，不一定在这些子集中。当 是一个完全完备码时，通过计算，包含在 ，中的点就可得到 与 的联系。推论 （；，）是正则的双凯莱图，是 的一个完全完备码，有下述结论成立：（）当 和 都不为空集，且 时，有 。（）当 为空集时，则 且 。当 为空集时，则 且 。证明根据定理得，是 的完全完备码，则（）的 个子集，是 （）的一个划分，其中 ，是 到自身的既单且满的映射，（）且 。中的 个元素与 中的 个元素都包含在 中，中的 个元素与 中的 个元素都包含在 中，因此有 。当 和 都不为空集，且 时，成立。若 为空集时，则 且 。若 为空集时，则 且 。注意若 是 的完全完备码时，的共轭不一定是 的完全完备码。但是，在一定条件下，和可以同时是完备码。引理 （；，）是正则双凯莱图，其中 （）。令 （），与 是 的子集。如果 ，则是完全完备码当且仅当 是完全完备码。特别地，在 图 （；，）中，只要 ，则 是完全完备码当且仅当 是完全完备码。证明假定 是完全完备码。任取，则有（）。由条件 （），则存在唯一的 ，使得（）（），或唯一的，使得（）。因此 （）或（），都是唯一确定。考虑到 ，故 中有且只有一个点与 相连。对于任意的，同理可得 有且只有一个点与 相连。当 是完全完备码时，同理可证 是完全完备码。在 图 （；，）中，假定 。如果 是 的完全完备码，任取，则 而且存在唯一的 ，使得（），因此 （），即 中有且只有一个点与相邻。对于任意的，同理可得 有且只有一个点与 相连。因此，是完全完备码。同理可证如果 是完备码，那么 也是完全完备码。推论 （；，）是正则的双凯莱图，这里 （），。令 （），与 是 的子集。对于任意的 ，若 是完全完备码，则 珓和（）珓是完全完备码。证明珓与（）珓分别是 与 在 的自同构下的像，根据引理 可得结论。定义 令 是图 到图 的一个满同态，：（）（）。如果对于任意的 （），（），（）：（）（），是一个既单且满的映射，称 是 到 的一个覆盖，称 （），（）第 期李建勋，等：双凯莱图的完全完备码 为 的纤维。若对任意的 （），有 （），则称 是 到 的 重覆盖。显然，图 的自同构是 到自身的 重覆盖。引理 是图 到图 的覆盖，若 是 的完全完备码，则 （）是 的一个完全完备码。令珔表示在 个点的完全图基础上，每个顶点添加一个自环所得到的图。定理 假定 （；，）是正则的双凯莱图，这里 是 到自身的一个既单且满的映射且满足（）。是 （）一个?拟正规子集。那么，存在一个 重覆盖 ：珔 ，（珔 ），使得 （），（），当且仅当 与 都是完全完备码。证明如果存在一个 重覆盖 ：珔 ，（珔 ），使 得（），（）。由于 和 都是珔 的完全完备码，根据引理 可知 和是 的完全完备码。再由于 是（）一个 拟正规子集，（），可得 与 都是 的完全完备码。反之，假定 与 都是 的完全完备码。根据定理 得 个子集，是 （）的一个划分。又 是 （）一个 拟正规子集，所以 个子集，（），既是 （）的一个划分，也是 的完全完备码。由完全完备码的定义，可以定义覆盖映射：珔 ，其中 个子集，分别是珔 的 个顶点的纤维。因而存在 ，（珚 ）使 得（），（），。作为一种特殊的情况，下述推论 显然成立。推论 （；，）是正则的双凯莱图，令 （），是 （）的一个 拟正规子集。若 （），那么 是完全完备码，当且仅当存在一个 重覆盖 ：珔 ，且存在 （珔 ），使得 （）。在 图 （；，）中，如果 是完全完备码，则对于 或 中任意一个点都有 或 中的唯一个点与之相邻，反之亦然。再根据命题 ，是?拟正规子集当且仅当对任意 ，。令 表示具有 个点的完全二部图，则有如下结论。定理 （；，），是 （）的一个子集，而且对任意的 ，有 ，。则存在一个 重覆盖 ：，（，），（）使得 （）（）且 （）（）当且仅当 是完全完备码。通过上述结论，最终可得到定理 。定理 （；，），是 （）的一个子集，对任意 ，有 ，则下面条件等价：（）是 的完全完备码。（）（）的 个子集（），（）是（）的一个划分，其中 。（），（）。（）存在覆盖映射 ：（，）（，），（，）使得 （）（）且 （）（）。子群完全完备码假定 是有限群，是 的子群。集合 ，是 的一个左横贯是指 ，且，是 在 中的互不相同的左陪集。类似的，可以定义 的一个右横贯。若对任意的 ，有 ，则称 是逆封闭的。令 ，称为 是 的一个共轭子群，。定理 假定 是有限群，是 的子群且 有一个逆封闭的左横贯 。则对任意的 ，是双凯莱图 （；，）的一个完全完备码。证明因为 个子集（），（），是 （）的一个划分。根据定理 ，对任意的 ，是 的完全完备码。定理 假定 是有限群，是 的子群，（；，）是一个正则双凯莱图，其中 是到自身的一个既单且满的映射且满足（）。对任意的 ，下述结论成立。（）（）是 的完全完备码，当且仅当 可以被划分成 个子集 ，也可以被划分成 个子集 ，。（）是 的完全完备码，当且仅当可以被划分成 个子集 ，也可以被划分成 个子集 ，烟台大学学报（自然科学与工程版）第 卷。证明根据定理 ，是 的完全完备码，当且仅当 个子集，是 （）的一个划分，其中 ，。因为（）（），当 时，有 （）（），否则 （）（）。因此，（）（）和 （）（），故结论（）成立。因为 当且仅当 ，所以结论（）是结论（）的特殊情况。推论 令 是一个交换群，（；，），是 （）一个子集。如果 ，则 是 的一个完全完备码，当且仅当存在一个 重 覆 盖 ：珔 ，且 存 在 （珔 ），使得 （）（）（），。证明令 作为 的一个单位自同构，根据命题 ，是一个?拟正规子集。显然，。又有 ，根据推论 可得上述结论。参考文献：，（）：，（）：邓芸萍，孙玉芹循环图的有效控制集 黑龙江大学自然科学学报，（）：，（）：，（）：王燕，张星交换群上 度凯莱图的完全完备码 数学的实践与认识，（）：，（）：，?，：，?，：，（，）：，：；（责任编辑李春梅）