第３７卷第１期烟台大学学报（自然科学与工程版）Ｖｏｌ．３７Ｎｏ．１２０２４年１月ＪｏｕｒｎａｌｏｆＹａｎｔａｉＵｎｉｖｅｒｓｉｔｙ（ＮａｔｕｒａｌＳｃｉｅｎｃｅａｎｄＥｎｇｉｎｅｅｒｉｎｇＥｄｉｔｉｏｎ）Ｊａｎ．２０２４文章编号：１００４８８２０（２０２４）０１００１６０５ｄｏｉ：１０．１３９５１／ｊ．ｃｎｋｉ．３７１２１３／ｎ．２２１１１３收稿日期：２０２２１１２１基金项目：山东省自然科学基金资助项目（ＺＲ２０２０ＭＡ０４４）。通信作者：王燕（ｗａｎｇ－ｙａｎ＠ｐｋｕ．ｏｒｇ．ｃｎ），教授，博士，主要研究方向为拓扑图论。双凯莱图的完全完备码李建勋，王燕（烟台大学数学与信息科学学院，山东烟台２６４００５）摘要：给出了正则双凯莱图存在完全完备码的若干充分必要条件，并给出了群的子群在其双凯莱图中可以作为完全完备码的充分必要条件。关键词：双凯莱图；完全完备码；覆盖中图分类号：Ｏ１５７６文献标志码：Ａ完备码（图论中也称为有效控制集）问题是基于图中顶点集合划分提出的，目的是利用图中的孤立点集将所有顶点进行划分。这种划分也是图模拟网络进行稳定性研究的一个重要方面。而完全完备码是利用图中的匹配来代替孤立点集来划分图的顶点集合，这样也增加了网络的稳定性。定义１假定Γ是一个图，Ｔ是顶点集Ｖ（Γ）的一个子集。若Γ的每一个点都与Ｔ中的唯一的一个点相邻，则称Ｔ是Γ的一个完全完备码。由定义可知，Ｔ中每一个点也恰好和它内部的一个点相邻，因而Ｔ是一个匹配。近些年来，点传递图尤其是凯莱图中的完全完备码问题受到了广泛关注。例如文献［１］刻画了二部凯莱图的完全完备码，并给出了某些循环Ｈａｒａｒｙ图存在完全完备码的充要条件。文献［２］给出了有限群的一个共轭封闭子集构成该群的凯莱图的完全完备码的充要条件。文献［３］给出了完备码个数为２的方幂的循环图存在完全完备码的充要条件以及给出了子群可作为完全完备码的一个充要条件。文献［４］刻画了奇素数度循环图中存在完全完备码的充要条件。文献［５］讨论了循环群上４度凯莱图的完全完备码问题。关于交换群上的凯莱图，文献［６］给出了交换群上４度凯莱图存在完全完备码的充要条件。本研究关注双凯莱图完全完备码的存在性问题。一般来说，双凯莱图不是点传递图，但是它是最接近点传递图的一类图。定义２设Ｈ是一个有限群，Ｒ，Ｌ，Ｓ是Ｈ的子集合，满足１Ｒ∪Ｌ，Ｒ＝Ｒ－１，Ｌ＝Ｌ－１。定义...
