关于图的距离标号数的研究

The distance labeling of a graph is a very active research field in the past 30 years, which originally comes from an abstract description of the channel assignment problem in a radio network, and also is a generalized coloring problem of graphs, with a certain theoretical research value and practical value. The project focuses on the index based on distance labeling, that is, the span of a graph. We try to find some effective methods to obtain the span of a graph by establishing the relationship between integer flow, tension and the span of a graph. On the other hand, we concentrate on the unsolved problem as following: Characterize finite trees with diameter at least 3 such that the L(2,1,1) span equals maximum edge degree. Finnally, we consider giving a complete characterization of caterpillers and trees with diameter at most 10. Our work may further broaden the research scope of distance labelings of graphs and try to get a better way to obtain the span of a graph.

图的距离标号问题是近 30 年来研究比较活跃的一个标号分支，最初源于对无线网络中频率分配问题的一种抽象描述，同时它也是图论中经典图着色理论的自然推广，具有重要的理论意义与应用价值。本项目主要研究图的距离标号数，即最小化标号之间的差。我们将试图通过建立图的标号数与整数流、tension之间的关系，以此来确定一些图类的标号数。此外，围绕一些尚未解决的问题展开研究，尝试给出 L(2,1,1) 标号数等于最大边度的树的充分条件，力求促进相关问题和猜想的解决。最后，在已被研究过的树类的基础上，尝试刻画其他各种重要树类（如毛毛虫树及直径不超过 10 的树等）的 L(2,1,1) 标号数。本项目将进一步扩大距离标号问题的研究范围，力求得到求一般图的标号数的更好方法。

图的距离标号问题是近30年来研究比较活跃的一个标号分支，最初源于对无线网络中频率分配问题的一种抽象描述，同时它也是图论中经典图着色理论的自然推广，具有重要的理论意义与应用价值。.本项目在国家自然科学基金委的资助及项目成员的共同努力下，完成了项目的主要目标，但在研究内容上略有调整。目前，项目组得到的主要结果有：.（1）从重边(heavy edge)的角度出发，我们得到多个达到上界（即L(2,1,1)跨度等于最大边度）的充分条件。利用这些充分条件，我们完全刻画了直径不超过6的树的L(2,1,1)跨度；.（2）根据对毛毛虫的坏点间的距离进行分类，我们得到了一些达到上界的充分条件。利用这些充分条件，我们完全刻画了最大边度不超过5的毛毛虫的L(2,1,1)跨度；.（3）我们完全确定了具有2n个顶点的(n-2)-正则二部图的L(1,1)及L(2,1)跨度；通过利用Lovász局部引理，给出了k-正则图的L(h1,h2)跨度的上界；.（4）我们也考虑同时优化两个目标，即阶和跨度，完全确定了一些特殊图类（如路，圈，正则图，树，毛毛虫等）在最小阶下的L(2,1)跨度。