青岛大学数学与统计学院，山东 青岛

收稿日期：2023年7月28日；录用日期：2023年8月30日；发布日期：2023年9月8日

摘要

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

关键词

列表L(2,1)-标号，平面图，圈

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

Mingyue Yang

School of Mathematics and Statistics, Qingdao University, Qingdao Shandong

Received: Jul. 28^th, 2023; accepted: Aug. 30^th, 2023; published: Sep. 8^th, 2023

ABSTRACT

The list L(2,1)-labelling can be applied to channel assignment problems which is an important optimization issue. The k-L(2,1)-labelling is a mapping $\phi :V\left(G\right)\to \left\{0,1,\cdots ,k\right\}$ of a graph G, such that $\left|\phi \left(u\right)-\phi \left(v\right)\right|\ge 2$ if $d\left(u,v\right)=1$ and $\left|\phi \left(u\right)-\phi \left(v\right)\right|\ge 1$ if $d\left(u,v\right)=2$ , where $d\left(u,v\right)$ is the distance between the vertex u and the vertex v in the graph. Denote ${\lambda }_{\left(2,1\right)}^l\left(G\right)=min\left\{k|Ghasalistk\text{-}L\left(2,1\right)\text{-}labelling\right\}$ be the list L(2,1)-labelling number. In 2018, Zhu and Bu et al. demonstrated the result that ${\lambda }_{\left(2,1\right)}^l\left(G\right)\le max\left\{\Delta +15,29\right\}$ for the planar graph G without 4-cycles and 6-cycles. In this paper we improve the upper bound of this result to ${\lambda }_{\left(2,1\right)}^l\left(G\right)\le max\left\{\Delta +12,24\right\}$ .

Keywords:List L(2,1)-Labelling, Planar Graph, Cycles

Copyright © 2023 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

本文只考虑简单图，有限图和无向图。如果图G是平面图，则它的边只在端点处相交并能在一个平面上表示出来。

平面图的L(2,1)-标号源于无线电发射机的信道分配问题。在1991年，Roberts [1] 提出了最优信道分配问题，即给无线电发射机分配频率，使接近的无线电发射机不受干扰并且使用的频率数量最小。随后，Griggs和Yeh [2] 给出了L(2,1)-标号的定义。在无线网络中，将无线电发射机视为图中的一个顶点，其中每个顶点都有自己的信道列表，然后从列表中选择一个，使得距离为2的顶点有不同的选择，相邻的顶点选择的信道至少相距2个信道。

k-L(2,1)-标号是指一个平面图满足映射 $\phi :V\left(G\right)\to \left\{0,1,\cdots ,k\right\}$ ，使得对任意点u和v，若 $d\left(u,v\right)=1$ ，则 $\left|\phi \left(u\right)-\phi \left(v\right)\right|\ge 2$ 且若 $d\left(u,v\right)=2$ ，则 $\left|\phi \left(u\right)-\phi \left(v\right)\right|\ge 1$ ，其中 $d\left(u,v\right)$ 是图中点u和点v之间的距离。记 ${\lambda }_{\left(2,1\right)}\left(G\right)=\min \left\{k|有一个k\text{-}L\left(2,1\right)\text{-}标号\right\}$ 是图G的L(2,1)-标号数。

若图G中的每个顶点v都有一个可容许标号集 $L\left(v\right)$ 且它可以选择其中一个元素作为它的标号，则称L为一个列表配置。设 $\left|L\left(v\right)\right|$ 是集合 $L\left(v\right)$ 的元素个数。若 $\left|L\left(v\right)\right|\ge k$ ，则称L是k-列表配置。对于一个(k + 1)-列表配置L，若图G有一个k-L(2,1)-标号，则称图G有一个列表L(2,1)-标号(简记为L-L(2,1)-标号)。设 ${\lambda }_{\left(2,1\right)}^l\left(G\right)=\min \left\{k|有一个L\text{-}L\left(2,1\right)\text{-}标号\right\}$ 为图G的L-L(2,1)-标号数。

图的列表L(2,1)-标号一直是一个研究热点。在1992年，Griggs和Yeh [2] 证明了 ${\lambda }_{\left(2,1\right)}\left(G\right)\le {\Delta }^2+2\Delta$ 并提出了下面的猜想。

猜想1 对于任意一个 $\Delta \ge 2$ 的平面图G， ${\lambda }_{\left(2,1\right)}\left(G\right)\le {\Delta }^2$ 。

目前，此猜想还没有被完全解决。但下面的结果已被证明。在1996年，Chang和Kuo [3] 证明了对于平面图G，有 ${\lambda }_{\left(2,1\right)}\left(G\right)\le {\Delta }^2+\Delta$ 。在2008年，Gon\c{c}alves [4] 改进了上面的结果并证明了 ${\lambda }_{\left(2,1\right)}\left(G\right)\le {\Delta }^2+\Delta -2$ 。Zhu和Lv等人 [5] 证明了若平面图G不含4-圈，5-圈，则有 ${\lambda }_{\left(2,1\right)}\left(G\right)\le \Delta +12$ 。Zhu和Hou等人 [6] 证明了若平面图G不含4-圈，则有 ${\lambda }_{\left(2,1\right)}\left(G\right)\le \Delta +19$ 。Zhou和Sun [7] 证明了若平面图G不含3-圈，相交4-圈，则有 ${\lambda }_{\left(2,1\right)}^l\left(G\right)\le \Delta +12$ 。Zhu和Bu等人 [8] 证明了若平面图G不含4-圈，6-圈，则有 ${\lambda }_{\left(2,1\right)}^l\left(G\right)\le \max \left\{\Delta +15,29\right\}$ 。其他相关的结论可见参考文献 [8] 。本文我们证明了下面的定理。

定理1若平面图G不含4-圈和6-圈，则有 ${\lambda }_{\left(2,1\right)}^l\left(G\right)\le \max \left\{\Delta +12,24\right\}$ 。

此定理与Zhu和Bu [8] 等人的结果相比，上界至少下降了3。与国内外研究动态相比，此定理具有很强的可行性，在短圈限制条件下， $\Delta +12$ 已经是一个比较小的上界了。

2. 一些概念和符号的说明

在平面图G中，我们用 $V\left(G\right)$ ， $E\left(G\right)$ 和 $F\left(G\right)$ 分别表示顶点集，边集，面集。它们可分别缩写为V，E，F。我们用 $d\left(v\right)$ 表示顶点v的度数，用 $d\left(f\right)$ 表示面f的度数。此外，最大度和最小度分别用 $\Delta \left(G\right)$ ， $\delta \left(G\right)$ 表示(分别简写为∆和δ)。顶点v是一个k-点， $k^{+}$ -点和 $k^{-}$ -点这分别意味着 $d\left(v\right)=k$ ， $d\left(v\right)\ge k$ 和 $d\left(v\right)\le k$ 。面f是一个k-面， $k^{+}$ -面和 $k^{-}$ -面，这分别意味着 $d\left(f\right)=k$ ， $d\left(f\right)\ge k$ 和 $d\left(f\right)\le k$ 。顶点v的k-邻点是指点v有一个度为k的邻点。设 $n_k\left(v\right)$ 为顶点v的k-邻点的个数。我们用 $d\left(u,v\right)$ 表示顶点u和顶点v之间的距离。若两个4-圈有一个公共点，则称它们相交。

我们用 $t\left(v\right)$ 表示与点v关联3-面的数量。若点v在3-面中，则称它为三角点，否则为非三角点。若 $d\left(v\right)=k$ 且v是一个三角点，则称v是一个三角k-点，否则他是一个非三角k-点。设[uvw]-面是一个顶点分别为u，v，w的3-面。设[x, y, z]-面是有 $d\left(u\right)=x$ ， $d\left(v\right)=y$ ， $d\left(w\right)=z$ 的[uvw]-面。在7⁺-面中，若三角4-点与非三角2-点相邻，则称它为坏4-点。若 $d\left(v\right)=k$ ，则v的邻点按顺时针方向分别表示为 $v_1,v_2,\cdots ,v_k$ 且点v邻点的度数分别为 $x_1,x_2,\cdots ,x_k$ 。设 $x_{k-1}\le x_k$ ，其中 $k\ge 2$ 且 $v_{k-1}$ 和 $v_k$ 同为三角点或非三角点。若 $x_1=3$ ，则设 $x_{11}$ ， $x_{12}$ 别为点 $v_1$ 除点v之外其余邻点的度数。

设 $d\left(v\right)=3$ 和 $x_1=3$ ，若 $x_2\ge 6$ 且 $x_3\ge 10$ ，则点v称为强3-点，否则称为弱3-点。

3. 主要结果的证明

在本节中，我们主要利用反证法和权转移规则给出证明过程。定义 $\left|F\left(v\right)\right|$ 为点v上的禁用标号数。假设图G是不满足定理的最小反例，设 $\max \left\{\Delta +12,24\right\}=a$ 。对于不含4-圈和6-圈的图G，我们有 ${\lambda }_{(2,1)}^l\left(G\right)>a$ 。为了便于证明，我们先给出图G的一些结构性质。在图G的结构特性证明过程中，我们通过删除图G的某条边或某个点可得到子图H。由于图G的最小性，H有满足定理的 ${\phi }^{\prime }$ 。我们通过将 ${\phi }^{\prime }$ 扩展到G的L-L(2,1)-标号 $\phi$ ，得到矛盾，其中 $L=a+1$ 。

引理1 [8] 平面图G是连通的且 $\delta \left(G\right)\ge 2$ 。

引理2 [8] G不含相邻的2-点。

引理3 如果 $f=\left[uvw\right]$ 是一个 $d\left(v\right)=2$ 的3-面，则 $d\left(u\right)+d\left(v\right)\le \Delta +9$ 。

证明 假设 $d\left(u\right)+d\left(v\right)\le \Delta +9$ 。我们知 $H=G-v$ 有一个L-L(2,1)-标号。因为 $F\left(v\right)\le d\left(u\right)+d\left(w\right)-4+6\le \Delta +11$ ， $\left|L\left(v\right)\right|-\left|F\left(v\right)\right|=2$ 。所以可以选择剩余两个数中的其中一个对图G中的点进行重新标号，这样得出了矛盾。

引理4 对于 $d\left(v\right)=3$ 的点v。

1) 如果 $x_1=2$ ，则要么 $v_2{v}_3\notin E$ ， $x_2\ge 4$ 和 $x_3\ge 10$ ，要么 $v_2{v}_3\in E$ ， $x_2\ge 9$ 和 $x_3\ge 9$ 。

2) 如果 $x_1=3$ ，则 $x_2\ge 6$ 和 $x_3\ge 10$ ，或 $x_{11}\ge 6$ 和 $x_{12}\ge 10$ 。对于 $v_2{v}_3\in E$ ，若 $x_1=3$ ，则 $x_2\ge 6$ 和 $x_3\ge 10$ ，或 $x_{11}\ge 6$ 和 $x_{12}\ge 10$ 。

证明 1) 假设 $x_2\le 3$ ( $v_2{v}_3\in E$ ， $x_2\le 8$ )。我们知 $H=G-v_1$ 有一个L-L(2,1)-标号。删除v本身的标号。因为 $F\left(v\right)\le 1+3-1+3+\Delta -1+3=\Delta +8$ ( $v_2{v}_3\in E$ , $F\left(v\right)\le 1+8-2+3+\Delta -2+3=\Delta +11$ )， $F\left(v_1\right)\le \Delta +4$ 。所以可以对G中的v，v₁依次重新标号，矛盾。

2) 假设 $x_2\le 5$ 和 $x_{11}\le 5$ 。我们知 $H=G-v{v}_1$ 有一个L-L(2,1)-标号。删除v，v₁本身的标号。因为 $F\left(v\right)\le 2+5-1+3+\Delta -1+3=\Delta +11$ ， $F\left(v_1\right)\le 2+5-1+3+\Delta -1+3=\Delta +11$ ，所以可以对G中的v和v₁分别进行重新标号，矛盾。对于 $v_2{v}_3\in E$ ，假设 $x_2\le 5$ 和 $x_{11}\le 5$ 。我们知 $H=G-v{v}_1$ 有一个L-L(2,1)-标号。删除v和v₁本身的标号。因为 $F\left(v\right)\le 2+5-2+3+\Delta -2+3=\Delta +9$ ， $F\left(v_1\right)\le 2+\Delta +5-2+6=\Delta +11$ 。我们能对G中的v，v₁依次进行重新标号，矛盾。

引理5 G无[3,3,7⁻]-面。

证明假设 $f=\left[uvw\right]$ 是一个3-面，其中 $d\left(u\right)=3$ ， $d\left(v\right)=3$ 且 $d\left(w\right)\le 7$ 。我们知 $H=G-uv$ 有一个L-L(2.1)-标号。删除u和v本身的标号。因为 $F\left(u\right)\le \Delta -1+3+7-2+3+1=\Delta +11$ ， $F\left(v\right)\le \Delta -1+3+1+7-2+3=\Delta +11$ ，所以我们能用剩下的两个数分别对u和v进行重新标号，矛盾。

引理6 假设 $d\left(v\right)=4$ ，则下面结论成立。

1) 如果 $x_1=x_2=2$ ，则要么 $v_3{v}_4\notin E$ ， $x_3\ge 4$ 和 $x_4\ge 10$ ，要么 $v_3{v}_4\in E$ ， $x_3\ge 8$ 和 $x_4\ge 9$ 。

2) 如果 $x_1=2$ ， $x_2=x_3=3$ ，则 $x_4\ge 10$ 。如果 $x_1=2$ ， $x_2=3$ 和 $x_3=4$ ，则 $x_4\ge 8$ 。

3) 如果 $x_1=x_2=x_3=3$ ，则 $x_4\ge 8$ 。

4) 对 $v_3{v}_4\in E$ 。如果 $x_1=2$ ， $x_2=3$ ，则G没有[3,4,4⁺]-面。其中若 $4\le x_3\le 7$ ，则 $x_4\ge 10$ 。

5) 对 $v_3{v}_4\in E$ 。如果 $x_1=2$ ， $4\le x_2\le 7$ ，则 $x_3+x_4\ge 13$ 。

6) 对 $v_3{v}_4\in E$ 。如果 $x_1=x_2=3$ ，则 $x_3+x_4\ge 13$ 。如果 $x_1=3$ ， $4\le x_2\le 7$ 和 $x_3=3$ ，则 $x_4\ge 5$ 。

7) 对 $v_1{v}_2\in E$ ， $v_3{v}_4\in E$ 。如果 $x_1=x_2=3$ ，则 $x_2\ge 5$ 且 $x_4\ge 5$ 。如果 $x_1=3$ ， $4\le x_2\le 6$ 和 $4\le x_3\le 6$ ，则 $x_4\ge 8$ 。

证明1) 假设 $x_3\le 3$ ( $v_3{v}_4\in E$ ， $x_3\le 7$ )。我们知 $H=G-v_1$ 有一个L-L(2,1)-标号。删除v， $v_2$ 上本身的标号。因为 $F\left(v\right)\le 2+3-1+3+\Delta -1+3=\Delta +9$ ( $v_3{v}_4\in E$ , $F\left(v\right)\le 2+7-2+3+\Delta -2+3=\Delta +11$ )， $F\left(v_2\right)\le \Delta +4$ ， $F\left(v_1\right)\le \Delta +4$ 。所以可以对G中的v，v₂，v₁依次进行重新标号，矛盾。

2) 假设 $x_4\le 9$ ( $x_4\le 7$ )。我们知 $H=G-v{v}_1$ 有一个L-L(2,1)-标号。删除v和v₁上本身的标号。因为 $F\left(v\right)\le 1+\left(3-1+3\right)\times 2+9-1+3=22$ ( $F\left(v\right)\le 1+3-1+3+4-1+3+7-1+3=21$ )， $F\left(v_1\right)\le \Delta -1+3+3=\Delta +5$ 。所以可以对G中的v和v₁依次进行重新标号，矛盾。

3) 假设 $x_4\le 7$ 。我们知 $H=G-v{v}_1$ 有一个L-L(2,1)-标号。删除v和v₁上本身的标号。因为 $F\left(v\right)\le 1+\left(3-1+3\right)\times 2+7-1+3=20$ ， $F\left(v_1\right)\le \Delta -1+3+3=\Delta +5$ 。所以可以对G中的v和v₁依次进行重新标号，矛盾。

4) 假设G有一个[3,4,4⁺]面，其中 $d\left(v\right)=4$ ， $x_3=3$ 和 $x_4\ge 4$ 。我们知 $\text{H}=G-v{v}_1$ 有一个L-L(2,1)-标号。删除v和v₁上本身的标号。因为 $F\left(v\right)\le 2+3-1+3+\Delta -2+3=\Delta +8$ ， $F\left(v_1\right)\le \Delta -1+3+3=\Delta +5$ 。所以可以对G中的v和v₁依次进行重新标号，矛盾。

假设 $x_4\le 9$ 。我们知 $H=G-v{v}_1$ 有一个L-L(2,1)-标号。删除v和v₁上本身的标号。因为 $F\left(v\right)\le 1+3-1+3+7-2+3+9-2+3=24$ ， $F\left(v_1\right)\le \Delta -1+3+3=\Delta +5$ 。所以可以对G中的v和v₁依次进行重新标号，矛盾。

5) 假设 $x_3+x_4\le 12$ 。我们知 $H=G-v{v}_1$ 有一个L-L(2,1)-标号。删除v和v₁上本身的标号。因为 $F\left(v\right)\le 1+7-1+3+12-4+6=24$ ， $F\left(v_1\right)\le \Delta -1+3+3=\Delta +5$ 。所以可以对G中的v和v₁依次进行重新标号，矛盾。

6) 假设 $x_3+x_4\le 12$ 。我们知 $H=G-v$ 有一个L-L(2,1)-标号。删除v上本身的标号。因为 $F\left(v\right)\le \left(3-1+3\right)\times 2+12-4+6=24$ 。所以可以对G中的v依次进行重新标号，矛盾。

7) 假设 $x_4\le 4$ 。我们知 $H=G-v{v}_3$ 有一个L-L(2,1)-标号。删除v和v₃上本身的标号。因为 $F\left(v\right)\le 3-1+3+7-1+3+1+4-2+3=20$ ， $F\left(v_3\right)\le \Delta -1+3+4-2+3+2=\Delta +9$ 。所以可以对G中的v和v₃依次进行重新标号，矛盾。

8) 假设 $x_2\le 5$ 。我们知 $H=G-v{v}_1$ 有一个L-L(2,1)-标号。删除v和v₁上本身的标号。因为 $F\left(v\right)\le 1+4-2+3+3-2+3+\Delta -2+3=\Delta +11$ ， $F\left(v_1\right)\le \Delta -1+3+4-2+3+2=\Delta +9$ 。所以可以对G中的v和v₁依次进行重新标号，矛盾。

9) 假设 $x_4\le 7$ 。我们知 $H=G-v{v}_1$ 有一个L-L(2,1)-标号。删除v和v₁上本身的标号。因为 $F\left(v\right)\le 1+6-2+3+6-2+3+7-2+3=23$ ， $F\left(v_1\right)\le \Delta -1+3+6-2+3+2=\Delta +11$ 。所以可以对G中的v和v₁依次进行重新标号，矛盾。

引理7假设 $d\left(v\right)=5$ ，则下列结论成立。

1) 如果 $x_1=x_2=x_3=2$ ，则要么 $v_4{v}_5\notin E$ 且 $x_4+x_5\ge 15$ ，要么 $v_4{v}_5\in E$ ， $x_4\ge 7$ 且 $x_5\ge 9$ 。

2) 如果 $x_1=x_2=2$ ， $x_3=3$ ，则要么 $v_4{v}_5\notin E$ 且 $x_4+x_5\ge 11$ ，要么 $v_4{v}_5\in E$ 且 $x_4+x_5\ge 13$ 。

3) 如果 $x_1=2$ ， $x_2=x_3=x_4=3$ 。则要么 $v_4{v}_5\notin E$ 且 $x_5\ge 4$ ，或 $v_4{v}_5\in E$ 且 $x_5\ge 8$ 。

4) 对 $v_4{v}_5\in E$ 。如果 $x_1=x_2=2$ ， $4\le x_3\le 7$ 和 $x_4=3$ ，则 $x_5\ge 8$ 。

5) 如果 $v_2{v}_3\in E$ ， $v_4{v}_5\in E$ ， $x_1=2$ 和 $x_2=x_4=3$ ，则 $x_3\ge 8$ 或 $x_5\ge 8$ 。

证明 1) 假设 $x_4+x_5\le 14$ ( $v_4{v}_5\in E$ , $x_4\le 6$ )。我们知 $H=G-v_1$ 有一个L-L(2,1)-标号。删除v，v₂和v₃上本身的标号。因为 $F\left(v\right)\le 3+14-2+6=21$ ( $v_4{v}_5\in E$ , $F\left(v\right)\le 3+6-2+3+\Delta -2+3=\Delta +11$ )， $F\left(v_2\right)\le \Delta -1+3+2=\Delta +4$ ， $F\left(v_3\right)\le \Delta -1+3+2=\Delta +4$ ， $F\left(v_1\right)\le \Delta -1+3+2=\Delta +4$ 。所以可以对G中的v，v₂，v₃和v₁依次进行重新标号，矛盾。

2) 假设 $x_4+x_5\le 10$ ( $v_4{v}_5\in E$ ， $x_4+x_5\le 12$ )。我们知 $H=G-v_1$ 有一个L-L(2,1)-标号。删除v和v₂上本身的标号。因为 $F\left(v\right)\le 2+3-1+3+10-2+6=21$ ( $v_4{v}_5\in E$ , $F\left(v\right)\le 2+3-1+3+12-4+6=21$ )， $F\left(v_2\right)\le \Delta -1+3+3=\Delta +5$ ， $F\left(v_1\right)\le \Delta -1+3+3=\Delta +5$ 。所以可以对G中的v，v₂和v₁依次进行重新标号，矛盾。

3) 假设 $x_5\le 3$ ( $v_4{v}_5\in E$ , $x_5\le 7$ )。我们知 $H=G-v{v}_1$ 有一个L-L(2，1)-标号。删除v和v₁上本身的标号。因为 $F\left(v\right)\le 1+\left(3-1+3\right)\times 4=21$ ( $v_4{v}_5\in E$ , $F\left(v\right)\le 1+\left(3-1+3\right)\times 2+3-2+3+7-2+3=23$ )， $F\left(v_1\right)\le \Delta -1+3+4=\Delta +6$ 。所以可以对G中的v和 $v_1$ 依次进行重新标号，矛盾。

4) 假设 $x_5\le 7$ 。我们知 $H=G-v{v}_1$ 有一个L-L(2,1)-标号。删除v，v₁和v₂上本身的标号。因为 $F\left(v\right)\le 2+7-1+3+3-2+3+7-2+3=23$ ， $F\left(v_2\right)\le \Delta -1+3+3=\Delta +5$ ， $F\left(v_1\right)\le \Delta -1+3+3=\Delta +5$ 。所以可以对G中的v，v₂和v₁依次进行重新标号，矛盾。

5) 假设 $x_3\le 7$ 和 $x_5\le 7$ 。我们知 $H=G-v{v}_1$ 有一个L-L(2,1)-标号。删除v，v₁，v₂和v₃上本身的标号。因为 $F\left(v_2\right)\le \Delta -1+3+7-2+3+1=\Delta +11$ ， $F\left(v_3\right)\le \Delta -1+3+7-2+3+1=\Delta +11$ ， $F\left(v\right)\le 3+\left(7-2+3\right)\times 2=19$ ， $F\left(v_1\right)\le \Delta -1+3+2=\Delta +4$ 。所以可以对G中的v₂，v₃，v和v₁依次进行重新标号，矛盾。

引理8 假设 $d\left(v\right)=6$ ，则下列结论成立。

1) 如果 $x_1=x_2=x_3=x_4=2$ ，则要么 $v_5{v}_6\notin E$ ， $x_5\ge 4$ 且 $x_6\ge 4$ ，要么 $v_5{v}_6\in E$ ， $x_5\ge 4$ 且 $x_6\ge 8$ 。

2) 如果 $x_1=x_2=x_3=2$ ， $x_4=3$ ，则要么 $v_5{v}_6\notin E$ 且 $x_5+x_6\ge 7$ ，要么 $v_5{v}_6\in E$ 且 $x_5+x_6\ge 11$ 。

证明 1) 假设 $x_5\le 3$ ( $v_5{v}_6\in E$ , $x_5\le 3$ )。我们知 $H=G-v_1$ 有一个L-L(2,1)-标号。删除v，v₂，v₃和v₄上本身的标号。因为 $F\left(v\right)\le 4+3-1+3+\Delta -1+3=\Delta +11$ ( $v_5{v}_6\in E$ , $F\left(v\right)\le 4+3-1+3+\Delta -1+3=\Delta +11$ )， $F\left(v_2\right)\le \Delta -1+3+2=\Delta +4$ ， $F\left(v_3\right)\le \Delta -1+3+2=\Delta +4$ ， $F\left(v_4\right)\le \Delta -1+3+2=\Delta +4$ ， $F\left(v_1\right)\le \Delta -1+3+2=\Delta +4$ 。所以可以对G中的v， $v_2$ ， $v_3$ ， $v_4$ 和 $v_1$ 依次进行重新标号，矛盾。

2) 假设 $x_5+x_6\le 6$ ( $v_5{v}_6\in E$ , $x_5+x_6\le 10$ )。我们知 $H=G-v{v}_1$ 有一个L-L(2,1)-标号。删除v，v₁，v₂和v₃上本身的标号。因为 $F\left(v\right)\le 3+3-1+3+6-2+6=18$ ( $v_5{v}_6\in E$ , $F\left(v\right)\le 3+3-1+3+10-4+6=20$ )， $F\left(v_3\right)\le \Delta -1+3+3=\Delta +5$ ， $F\left(v_2\right)\le \Delta -1+3+3=\Delta +5$ ， $F\left(v_1\right)\le \Delta -1+3+3=\Delta +5$ 。所以可以对G中的v，v₃，v₂，v₁依次进行重新标号，矛盾。

引理9 假设 $d\left(v\right)=7$ ，则下列结论成立。

如果 $x_1=x_2=\cdots =x_5=2$ ，则要么 $v_6{v}_7\notin E$ ， $x_6+x_7\ge 7$ ，要么 $v_6{v}_7\in E$ ， $x_6\ge 4$ 且 $x_7\ge 4$ 。

证明 假设 $x_6+x_7\le 6$ ( $v_6{v}_7\in E$ , $x_6\le 3$ )。我们知 $H=G-v_1$ 有一个L-L(2,1)-标号。删除v，v₂， $\cdots$ ，v₅上本身的标号。因为 $F\left(v\right)\le 5+6-2+6=15$ ( $v_6{v}_7\in E$ , $F\left(v\right)\le 5+3-2+3+\Delta -2+3=\Delta +10$ )， $F\left(v_2\right)\le \Delta -1+3+2=\Delta +4$ ， $\cdots$ ， $F\left(v_5\right)\le \Delta -1+3+2=\Delta +4$ ， $F\left(v_1\right)\le \Delta -1+3+2=\Delta +4$ 。所以可以对G中的v，v₁₌₂， $\cdots$ ，v₅，v₁依次进行重新标号，矛盾。

引理10 假设 $d\left(v\right)=8$ ，则下列结论成立。

如果 $x_1=x_2=\cdots =x_7=2$ ，则 $x_8\ge 6$ 。如果 $x_1=x_2=\cdots =x_6=2$ 且 $v_7{v}_8\in E$ ，则 $x_7+x_8\ge 13$ 。

证明 假设 $x_8\le 5$ 。我们知 $H=G-v_1$ 有一个L-L(2,1)-标号。删除v，v₂， $\cdots$ ，v₇上本身的标号。因为 $F\left(v\right)\le 7+5-1+3=14$ ， $F\left(v_2\right)\le \Delta -1+3+1=\Delta +3$ ， $\cdots$ ， $F\left(v_7\right)\le \Delta -1+3+1=\Delta +3$ ， $F\left(v_1\right)\le \Delta -1+3+1=\Delta +3$ 。所以可以对G中的v，v₂， $\cdots$ ，v₇，v₁依次进行重新标号，矛盾。

假设 $x_7+x_8\le 12$ 。我们知 $H=G-v{v}_1$ 有一个L-L(2,1)-标号。删除v，v₁， $\cdots$ ，v₆上本身的标号。因为 $F\left(v\right)\le 6+12-4+6=20$ ， $F\left(v_1\right)\le \Delta -1+3+2=\Delta +4$ ， $\cdots$ ， $F\left(v_6\right)\le \Delta -1+3+2=\Delta +4$ 。所以可以对G中的v，v₁， $\cdots$ ，v₆依次进行重新标号，矛盾。

引理11 假设 $d\left(v\right)=9$ ，则下列结论成立。

如果 $x_1=x_2=\cdots =x_8=2$ ，则 $x_9\ge 3$ 。

证明 假设 $x_9\le 2$ 。我们知 $H=G-v_1$ 有一个L-L(2.1)-标号。删除v，v₂， $\cdots$ ，v₈上本身的标号。因为 $F\left(v\right)\le 8+2-1+3=12$ ， $F\left(v_2\right)\le \Delta -1+3+1=\Delta +3$ ， $\cdots$ ， $F\left(v_8\right)\le \Delta -1+3+1=\Delta +3$ ， $F\left(v_1\right)\le \Delta -1+3+1=\Delta +3$ 。所以可以对G中的v，v₂， $\cdots$ ，v₈，v₁依次进行重新标号，矛盾。

4. 定理的证明

设G是连通图，则由欧拉公式 $\left|V\right|-\left|E\right|+\left|F\right|=2$ 和公式 ${\displaystyle \underset{v\in V}{\sum }d\left(v\right)}={\displaystyle \underset{f\in F}{\sum }d\left(f\right)}=2\left|E\right|$ 知：

${\displaystyle \underset{v\in V}{\sum }\left(\frac{3}{2}d\left(v\right)-5\right)}+{\displaystyle \underset{f\in F}{\sum }\left(d\left(f\right)-5\right)}=-10$ 。

设 $w\left(v\right)=\frac{3}{2}d\left(v\right)-5$ ， $w\left(f\right)=d\left(f\right)-5$ 。其中对于 $x\in V\cup F$ ，令 $w\left(x\right)$ 为初始权函数。基于上面的结

构特性选择恰当的权转移规则去重新分配这些权值，从而得到一个新的权值。记 $w^{\prime }\left(x\right)$ 为最后一次权转移后的权函数，其中 $x\in V\cup F$ 。在完成权转移过程之后，权值的和是不会发生变化的。

然而，我们对于所有的 $x\in V\cup F$ ，得到的 $w^{\prime }\left(x\right)$ 是一个非负数。于是就产生了下面的矛盾。

$\text{0}\le {\displaystyle \underset{x\in V\cup F}{\sum }{w}^{\prime }\left(x\right)}={\displaystyle \underset{x\in V\cup F}{\sum }w\left(x\right)}=-10<0$ 。

进而证明上述极小反例不存在，从而证明定理1是成立的。

下面给出具体的权转移规则。

R1 每个7⁺-面给它相邻的3-面 $\frac{\text{1}}{\text{6}}$ 。

R2 每个3-面从它关联的每个点得 $\frac{\text{1}}{\text{2}}$ 。

R3 每个非三角2-点从它相邻的3⁺-点得1。每个三角2-点从它相邻的10⁺-点得 $\frac{\text{5}}{\text{4}}$ 。

R4.1 对于 $uv\in E$ ，设v是一个非三角3-点。若 $4\le d\left(u\right)\le 9$ ，则点u给点v转 $\frac{\text{1}}{\text{2}}$ 。若 $d\left(u\right)\ge 10$ ，则点u给点v转1。

R4.2 对于三角3-点v，设 $f=\left[uvw\right]$ 是一个关联点v的3-面。表1说明了点u给点v转权的各个情况。

表1. 三角3-点v

R4.3 强3-点给它相邻的弱3-点转 $\frac{\text{1}}{\text{2}}$ 。

R5.1 对于 $uv\in E$ ，设v是一个非三角4-点。若 $8\le d\left(u\right)\le 9$ ，则点u给点v转 $\frac{\text{1}}{\text{2}}$ 。若 $d\left(u\right)\ge 10$ ，则点u给点v转1。

R5.2 对于三角4-点v，设 $f=\left[uvw\right]$ 是一个关联点v的3-面。表2说明了点u给点v转权的各个情况。

表2. 三角4-点v

R6.1 对于 $uv\in E$ ，设v是一个非三角5-点。若 $8\le d\left(u\right)\le 11$ ，则点u给点v转 $\frac{\text{1}}{\text{2}}$ 。若 $d\left(u\right)\ge 12$ ，则点u给点v转1。

R6.2 对于三角5-点v，设 $f=\left[uvw\right]$ 是一个关联点v的3-面。表3说明了点u给点v转权的各个情况。

表3. 三角5-点v

R7 对于三角6-点v，设 $f=\left[uvw\right]$ 是一个关联点v的3-面。表4说明了点u给点v转权的各个情况。

表4. 三角6-点v

R8 7⁺-面给他相邻的坏4-点转 $\frac{\text{1}}{\text{4}}$ 。

接下来我们验证：对 $\forall x\in V\cup F$ ， $w^{\prime }\left(x\right)\ge 0$ 。首先验证所有的面， $w^{\prime }\left(f\right)\ge 0$ ， $f\in F$ 。

如果 $d\left(f\right)=3$ ， $w\left(f\right)=3-5=-2$ 。因为平面图G不含4-圈和6-圈，所以3-面必与7⁺-面相邻。

由R1，R2知： $w^{\prime }\left(f\right)\ge -2+\frac{1}{6}\times 3+\frac{1}{2}\times 3=0$ 。

如果 $d\left(f\right)=5$ ，则 $w^{\prime }\left(f\right)=w\left(f\right)=d\left(f\right)-5=0$ 。

对于 $d\left(f\right)=7$ 的面f。若7⁺-面不关联坏4-点，则7⁺-面至多关联 $d\left(f\right)$ 个3-面。由R1得， $w^{\prime }\left(f\right)\ge d\left(f\right)-5-\frac{1}{6}d\left(f\right)=\frac{5}{6}d\left(f\right)>0$ 。若7⁺-面关联坏4-点。我们使7⁺-面关联最多的坏4-点和邻最多的3-面，即在7⁺-面中非三角2-点的邻点都是坏4-点且7⁺-面中剩余的边都与3-面相邻。设 $n_{3f}$ 为与7⁺-面相邻的3-面的数量且 $n_{bad}$ 为与7⁺-面关联的坏4-点的数量。由引理2，我们得到了下列的关系， $d\left(f\right)=n_{3f}+n_{bad}$ 。因为坏4-点可以包含7⁺-面上的3个点，与7⁺-面相邻的3-面可以与7⁺-面上的2个非三角2-点相邻。所以我们得到 $n_{bad}=\lfloor \frac{d\left(f\right)}{3}\rfloor \times 2$ 。由R1，R8得， $w^{\prime }\left(f\right)\ge d\left(f\right)-5-\frac{1}{6}\left[d\left(f\right)-n_{bad}\right]-\frac{1}{4}{n}_{bad}=\lceil \frac{7}{9}d\left(f\right)\rceil -5>0$ 。

然后验证所有的点， $w^{\prime }\left(v\right)\ge 0$ ，其中 $v\in V$ 。由引理1知， $\delta \left(G\right)\ge 2$ ，因此我们考虑2⁺-点。

1) $d\left(v\right)=2$ ， $w\left(v\right)=\frac{3}{2}\times 2-5=-2$ 。若点v是一个非三角点，则由引理2，点v与2个3⁺-点相邻。由R3得， $w^{\prime }\left(v\right)\ge -2+1\times 2=0$ 。若点v是一个三角点，则由引理3，点v与2个10⁺-点相邻。

由R3得， $w^{\prime }\left(v\right)\ge -2-\frac{1}{2}+\frac{5}{4}\times 2=0$ 。

2) $d\left(v\right)=3$ ， $w\left(v\right)=\frac{3}{2}\times 3-5=-\frac{1}{2}$ 。由引理4知， $n_2\left(v\right)\le 1$ 。

$t\left(v\right)=0$ ，设 $x_1\le x_2\le x_3$ 。如果 $n_2\left(v\right)=1$ ，设 $x_1=2$ ，则由引理4(1)知， $x_2\ge 4$ 和 $x_3\ge 10$ 。由R3，R4.1得， $w^{\prime }\left(v\right)\ge -\frac{1}{2}-1+\frac{3}{2}=0$ 。如果 $n_2\left(v\right)=0$ ，设 $x_1=3$ 。若 $x_2\le 5$ 或 $x_3\le 9$ ，则由引理4(2)知， $x_{11}\ge 6$ 和 $x_{12}\ge 10$ 。所以v是一个弱3-点，和v₁是一个强3-点。由R4.3得， $w^{\prime }\left(v\right)\ge -\frac{1}{2}+\frac{1}{2}=0$ 。如果 $x_2\ge 6$ 和 $x_3\ge 10$ ，则v 是一个强3-点。由R4.1，R4.3得， $w^{\prime }\left(v\right)\ge -\frac{1}{2}-\frac{1}{2}+\frac{1}{2}+1=\frac{1}{2}>0$ 。

设 $x_3\ge x_2\ge x_1\ge 4$ ，由R4.1得， $w^{\prime }\left(v\right)\ge -\frac{1}{2}+\frac{1}{2}\times 3=1>0$ 。

$t\left(v\right)=1$ ，设 $v_2{v}_3\in E$ 和 $x_2\le x_3$ 。由引理3知，v₂和v₃不是2-点。如果 $n_2\left(v\right)=1$ ，设 $x_1=2$ ，则由引理4(1)知 $x_2\ge 9$ 和 $x_3\ge 9$ 。由R2，R3，R4.2得， $w^{\prime }\left(v\right)\ge -\frac{1}{2}-1-\frac{1}{2}+1\times 2=0$ 。如果 $n_2\left(v\right)=0$ ，设 $x_1=3$ 。若 $x_2\le 5$ 或 $x_3\le 9$ ，则由引理4(2)知， $x_{11}\ge 6$ 和 $x_{12}\ge 10$ 。因此v是一个弱3-点和v₁是一个强3-点。如果 $x_2=3$ ，则由引理5知， $x_3\ge 8$ 。由R2，R4.2，R4.3得， $w^{\prime }\left(v\right)\ge -\frac{1}{2}-\frac{1}{2}+\frac{1}{2}+\frac{1}{2}=0$ 。如果 $x_3\ge x_2\ge 4$ ，则由R2，R4.2，R4.3得， $w^{\prime }\left(v\right)\ge -\frac{1}{2}-\frac{1}{2}+\frac{1}{2}+\frac{1}{4}\times 2=0$ 。如果 $x_2\ge 6$ 和 $x_3\ge 10$ ，则v是一个强3-点。由R2，R4.2，R4.3得， $w^{\prime }\left(v\right)\ge -\frac{1}{2}-\frac{1}{2}-\frac{1}{2}+\frac{3}{2}=0$ 。设 $x_1\ge 4$ 。如果 $x_2=3$ ，则由引理5知， $x_3\ge 8$ 。由R2，R4.1，R4.2得， $w^{\prime }\left(v\right)\ge -\frac{1}{2}-\frac{1}{2}+\frac{1}{2}+\frac{1}{2}=0$ 。如果 $x_3\ge x_2\ge 4$ ，则由R2，R4.1，R4.2得， $w^{\prime }\left(v\right)\ge -\frac{1}{2}-\frac{1}{2}+\frac{1}{2}+\frac{1}{4}\times 2=0$ 。

3) $d\left(v\right)=4$ ， $w\left(v\right)=\frac{3}{2}\times 4-5=1$ 。由引理6知， $n_2\left(v\right)\le 2$ 。

$t\left(v\right)=0$ ， $x_1\le x_2\le x_3\le x_4$ 。如果 $n_2\left(v\right)=2$ ，设 $x_1=x_2=2$ ，则由引理6(1)知， $x_3\ge 4$ 和 $x_4\ge 10$ 。由R3，R5.1得， $w^{\prime }\left(v\right)\ge 1-1\times 2+1=0$ 。如果 $n_2\left(v\right)=1$ ，设 $x_1=2$ 和 $x_2=x_3=3$ ，则由引理6(2)知， $x_4\ge 10$ 。由R3，R4.1，R5.1得， $w^{\prime }\left(v\right)\ge 1-1-\frac{1}{2}\times 2+1=0$ 。设 $x_2=3$ ， $x_3=4$ ，则由引理6(2)知， $x_4\ge 8$ 。由R3，R4.1，R5.1得， $w^{\prime }\left(v\right)\ge 1-1-\frac{1}{2}+\frac{1}{2}=0$ 。设 $x_4\ge x_3\ge x_2\ge 4$ ，由R3得， $w^{\prime }\left(v\right)\ge 1-1=0$ 。如果 $n_2\left(v\right)=0$ ，设 $x_1=x_2=x_3=3$ ，则由引理6(3)知， $x_4\ge 8$ 。由R4.1，R5.1得， $w^{\prime }\left(v\right)\ge 1-\frac{1}{2}\times 3+\frac{1}{2}=0$ 。设 $x_2\ge x_1\ge 3$ 和 $x_4\ge x_3\ge 4$ ，由R4.1得， $w^{\prime }\left(v\right)\ge 1-\frac{1}{2}\times 2=0$ 。

$t\left(v\right)=1$ ，设 $v_3{v}_4\in E$ ， $x_1\le x_2$ 和 $x_3\le x_4$ 。由引理3知，v₃和v₄均不是2-点。如果 $n_2\left(v\right)=2$ ，设 $x_1=x_2=2$ ，则由引理6(1)知 $x_3\ge 8$ ， $x_4\ge 9$ 。由R2，R3，R5.2得， $w^{\prime }\left(v\right)\ge 1-1\times 2-\frac{1}{2}+\frac{1}{2}+1=0$ 。如果 $n_2\left(v\right)=1$ ，设 $x_1=2$ ，则v是一个坏4-点。设 $x_2=3$ 。由引理6(4)， $x_4\ge x_3\ge 4$ 。如果 $x_3=4$ ，则由引理6(4)知， $x_4\ge 10$ 。由R2，R3，R4.1，R5.2，R8知， $w^{\prime }\left(v\right)\ge 1-1-\frac{1}{2}-\frac{1}{2}+\frac{1}{4}+\frac{3}{4}=0$ 。如果 $5\le x_3\le 7$ ，则由引理6(4)知， $x_4\ge 10$ 。由R2，R3，R4.1，R5.2得， $w^{\prime }\left(v\right)\ge 1-1-\frac{1}{2}-\frac{1}{2}+1=0$ 。如果 $x_3\ge 8$ 和 $x_4\ge 8$ ，则由R2，R3，R4.1，R5.2得， $w^{\prime }\left(v\right)\ge 1-1-\frac{1}{2}-\frac{1}{2}+\frac{1}{2}\times 2=0$ 。设 $4\le x_2\le 7$ ，则由引理6(5)知， $x_3+x_4\ge 13$ 。因此 $\left(x_3,x_4\right)\in \left\{\left(3,{10}^{+}\right),\left(4,9^{+}\right),\left(5,8^{+}\right),\left(6,7^{+}\right),\left(7^{+},7^{+}\right)\right\}$ ，由R4.2和R5.2知，v₃和v₄至少给点v转 $\frac{1}{2}$ ，再由R2，R3得， $w^{\prime }\left(v\right)\ge 1-1-\frac{1}{2}+\frac{1}{2}=0$ 。设 $x_2\ge 8$ 。如果 $x_3=3$ ， $4\le x_4\le 9$ ，则由R2，R3，R4.2，R5.1，R8得， $w^{\prime }\left(v\right)\ge 1-1-\frac{1}{2}+\frac{1}{2}-\frac{1}{4}+\frac{1}{4}=0$ 。如果 $x_3=3$ ， $x_4\ge 10$ ，由R2，R3，R4.2，R5.1，R8得， $w^{\prime }\left(v\right)\ge 1-1-\frac{1}{2}+\frac{1}{2}-\frac{1}{2}+1=\frac{1}{2}>0$ 。如果 $x_3\ge 4$ ， $x_4\ge 4$ ，由R2，R3，R5.1得， $w^{\prime }\left(v\right)\ge 1-1-\frac{1}{2}+\frac{1}{2}=0$ 。如果 $n_2\left(v\right)=0$ ，设 $x_1=x_2=3$ ，则由引理6(6)知， $x_3+x_4\ge 13$ 。因此 $\left(x_3,x_4\right)\in \left\{\left(3,{10}^{+}\right),\left(4,9^{+}\right),\left(5,8^{+}\right),\left(6,7^{+}\right),\left(7^{+},7^{+}\right)\right\}$ ，由R4.2和R5.2知，v₃和v₄至少给点v转 $\frac{1}{2}$ 。再由R2，R4.1得， $w^{\prime }\left(v\right)\ge 1-\frac{1}{2}\times 2-\frac{1}{2}+\frac{1}{2}=0$ 。设 $x_1=x_3=3$ ， $4\le x_2\le 7$ 。由引理6(6)得 $x_4\ge 5$ 。如果 $5\le x_4\le 7$ ，由R2，R4.1，R4.2，R5.2得， $w^{\prime }\left(v\right)\ge 1-\frac{1}{2}-\frac{1}{2}-\frac{1}{4}+\frac{1}{4}=0$ 。如果 $x_4\ge 8$ ，由R2，R4.1，R4.2，R5.2得， $w^{\prime }\left(v\right)\ge 1-\frac{1}{2}-\frac{1}{2}-\frac{1}{2}+\frac{1}{2}=0$ 。设 $x_1=x_3=3$ ， $x_2\ge 8$ 。由引理5知， $x_4\ge 4$ 。由R2，R4.1，R4.2，R5.1得， $w^{\prime }\left(v\right)\ge 1-\frac{1}{2}-\frac{1}{2}-\frac{1}{2}+\frac{1}{2}=0$ 。设 $x_1=3$ ， $x_2\ge 4$ ， $x_3\ge 4$ ， $x_4\ge 4$ 。由R2，R4.1得， $w^{\prime }\left(v\right)\ge 1-\frac{1}{2}-\frac{1}{2}=0$ 。设 $x_1\ge 4$ ， $x_2\ge 4$ ， $x_3\ge 3$ 。由引理5知， $x_4\ge 4$ ，则由R2，R4.2得， $w^{\prime }\left(v\right)\ge 1-\frac{1}{2}-\frac{1}{2}=0$ 。