不含4-圈和6-圈平面图的最优列表L(2,1)-标号

Optimal List L(2,1)-Labelling without 4-Cycles and 6-Cycles of Planar Graphs

摘要: 列表L(2,1)-标号是一个重要的可以应用到信道分配问题中的优化问题，k-L(2,1)-标号是指对于一个平面图G满足映射ϕ :V (G)→{0,1,…,k}，使得若d(u,v)=1，则|ϕ(u)−ϕ(v)|≥2；；若d(u,v)=2，则|ϕ(u)−ϕ(v)|≥1，其中d(u,v)是图中点u和点v之间的距离。记λ_(2,1)^l(G)=min{k|G有一列k-L(2,1)-标号}是列表L(2,1)-标号数。在2018年，Zhu and Bu等人在全局最优化杂志中得出这样一个结论：对于不含4-圈和6-圈的平面图G有λ_(2,1)^l(G)≤max{Δ+15,29}。本文改进了这个结论的上界λ_(2,1)^l(G)≤max{Δ+12,24}。

Abstract: The list L(2,1)-labelling can be applied to channel assignment problems which is an important op-timization issue. The k-L(2,1)-labelling is a mapping ϕ :V (G)→{0,1,…,k} of a graph G, such that |ϕ(u)−ϕ(v)|≥2 if d(u,v)=1 and |ϕ(u)−ϕ(v)|≥1 if d(u,v)=2, where d(u,v) is the distance between the vertex u and the vertex v in the graph. Denote λ_(2,1)^l(G)=min{k|G has a list k-L(2,1)-labelling} be the list L(2,1)-labelling number. In 2018, Zhu and Bu et al. demonstrated the result that λ_(2,1)^l(G)≤max{Δ+15,29} for the planar graph G with-out 4-cycles and 6-cycles. In this paper we improve the upper bound of this result to λ_(2,1)^l(G)≤max{Δ+12,24}.