图的距离二标号问题

图的距离二标号是经典点着色的一个自然推广，它在资源分配问题特别是频道分配问题中有极其重要的应用，受到多个领域学者们的极大关注，目前已经成为国内外研究的热点。该领域还有许多有挑战性的问题没有解决。本课题采用理论分析和数值实验的方法，从理论和算法两个方面对图的距离二标号问题进行深入研究。探索图的距离二标号数的行为规律以及它们所反映出的图的结构特征，揭示图的距离二标号数与图的其他参数之间的关系，设计求解一些重要图类距离二标号数的有效算法。有望在图的距离二圆标号、边标号和多重标号等问题上取得重要进展。本课题的研究成果将为图的着色理论作出贡献，为距离标号问题的进一步研究提供基础，开辟新的研究方向，为着色理论在频道分配等实际问题中的应用提供理论基础、数学模型以及相应的算法，具有重大理论意义和实际应用前景。

图的染色问题是图论中的热点问题之一。图的距离二标号是经典染色的自然推广，它们在频道分配问题中有很重要的应用。本项目对距离二标号问题进行了深入系统的研究，在几个关键问题上取得了实质性进展。（1）研究图的n重L(j,k)-标号问题,得到n重L(j,k)-标号数的基本性质以及它与其他参数的关系等，对三类网格图基本确定了它们的n重L(j,k)-标号数和n重L(j,k)-圆标号数，一部分结果已经发表在DAM上，另一部分结果已被JOCO接受。（2）研究图的距离二边标号，对四类网格图确定了它们的L(2,1)-边标号数或给出好的上下界，这些结果已被JOCO接受。确定了无穷正则树和低维立方体圆L(2,1)-边标号数，结果发表在TJM上。其他一些结果发表在Ars上。（3）提出图的组路覆盖的概念，研究了它与图的L(j,1)-和L(j,k)-标号数之间的关系，这些结果写成两篇论文已经发表在IPL上。（4）研究乘积图的距离二标号，所得结果一部分已经发表在Ars上，一些结果则已被接受或在投稿审理阶段。（5）对j不大于k的情形，确定了树和两个完全图乘积的圆L(j,k)-标号数，结果发表在J.Southeast University上。（6）研究图的多重集染色问题，解决了r方圈上的一个猜想，结果发表在IPL上；研究邻点可区别的全染色，对三正则图得到了很好的结果，这些结果已经投稿。以上研究成果推动了相关染色问题及其应用的研究，具有重要的理论意义和应用价值。为了使距离二标号的研究更加符合频道分配问题的实际需要，我们提出t分离的多重L(j,k)-标号以及放松的距离标号等问题并展开研究，目前已经取得一些实质性结果，可望取得更大的突破和更多的创新。