整循环图的平面性、独立数与边着色性质研究

"整循环图的一些新性质 (2012年)" 本文探讨了整循环图这一特殊图论结构的若干新特性，主要集中在它们的平面性、独立数以及边着色数。整循环图Xn(D)是由整数集合Zn={0,1,2,...,n-1}构成的顶点集，其中两个顶点a和b之间存在边连接，当且仅当它们的差的最高公约数gcd(a-b,n)属于集合D，D是n的一个正的真因子集。整循环图是循环图的一个子类，其特点是具有整谱，即图的特征多项式的根全为整数。 在引言部分，作者提到了Cayley图的概念，这是一种由群G和群G中的不包含单位元的生成集S定义的图，其中顶点集为G，边连接由群运算规则决定。整图是指具有整谱的图，而循环图G(n,5)是在模n剩余类环Zn上构建的，每个顶点与其余的151个顶点通过边相连，形成一个n阶的简单图。整循环图是循环图的特殊情况，满足特定的整数条件。 文章进一步深入研究了单位Cayley图Xn，这是在模n剩余类环Zn上基于单位群Un定义的图，其顶点集为Zn={0,1,2,...,n-1}，边连接规则为gcd(a-b,n)=1。单位Cayley图Xn具有正则性，每个顶点的度数等于欧拉函数φ(n)。Dejter和Giudici在1995年的研究中指出，当n为偶数时，Xn是2部图；而当n=2^k，k为非负整数时，Xn是完全2-部图。 论文的主要贡献在于对整循环图的平面性、独立数和边着色数的分析。平面性是图论中的一个重要属性，指图能否在平面上画出，使得任何两条边不相交（除了可能在端点处）。独立数则指的是图中可以选取的最大数量的不相邻顶点，这些顶点组成一个独立集。边着色数是将图的每条边涂上颜色，要求相邻边颜色不同所需的最少颜色数。作者不仅研究了这些性质，而且完全确定了整循环图的最大匹配大小，匹配是图中的一组边，没有共同的顶点。 整循环图的研究有助于深化我们对图论的理解，特别是其在编码理论、网络设计和密码学等领域有潜在的应用价值。通过深入研究这些性质，可以发现新的图的构造方法，优化网络布局，以及在数据传输和信息安全中寻找更有效的算法和协议。本文的工作为整循环图的理论框架增添了新的内容，为进一步的图论研究提供了有价值的参考。