路的积图的3- 距离染色

2021-01-22代青昂毛

科学技术创新 2021年3期

代青昂毛

（西北民族大学数学与计算机科学学院，甘肃兰州730030）

1 概述

图的距离染色是由F. Kramer 与H. Kramer 于1969 年首次在文献[1]中提出的，后来在文献[2]中被表述为k- 距离染色。所谓图的k- 距离染色是指图中距离不超过k 的顶点染不同颜色的点染色，其中k 为正整数. 为了研究图G的k- 距离染色数，Kramer 等人在文献[3]中定义了图G 的k- 方图，得到了图G 的k- 方图距离色数与k- 距离色数相等的结论。关于图的积图的距离染色，Kim 在文献[4] 中研究m阶路Pm与n 阶圈Cn 的直积Pm×Cn的2- 距离染色，证明了Pm×Cn的2- 距离染色数等于5 或6。Kim在文献[5]中研究了圈的笛卡尔积的2- 距离染色。Fertin 等在文献[6]中得到了路的笛卡尔积的k- 距离色数。

本文研究路的半强积与强积的3- 距离染色。图的半强积与强积的定义具体如下：

定义1.1[7]设有G 和H 两个简单图，图G 和H 的半强积G·H有顶点集V（G·H）=V（G）×V（H），任意两个顶点（u1，v1）与（u2，v2）相邻当且仅当u1u2∈E（G）且v1v2∈E（H），或者u1=u2且v1v2∈E（H）。

在后文中要用到以下引理：

引理1.1[2]对图G的任意子图H，有χk（H）≤χk（G）。

2 主要结论及其证明

设Pm=u0u1…um-1与Pn=v0v1…vn-1分别为m≥2 阶和n≥2 阶路。为了方便在直角坐标系中研究，把顶点（uy，vx）记为（x，y），其中x=0，1，…，n-1，y=0，1，…，m-1。记（x）k=x（mod k），其中x为整数。

关于路的半强积的3- 距离染色，有以下定理2.1- 定理2.3。

定理2.1 对任意的整数n≥4，有χ3（P2·Pn）=8。

证明P2·P4中任意两点之间的距离不超过3，并且顶点数等于8，所以χ3（P2·Pn）=8。由于P2·P4包含于P2·Pn，根据引理1.1 可知，χ3（P2·Pn）≥8。为证明χ3（P2·Pn）≤8，仅需用8 种颜色构造一个P2·Pn的3- 距离染色。对x=0，1，…，n-1，y=0，1，令σ（x，y）=（x+2y）8。显然，σ 所用颜色集为{0，1，2，…，7}。

现在证明σ 是P2·Pn的3- 距离染色。在P2·Pm中取任意顶点u=（x，y），那么与之任意距离不超过3 的顶点可能为v（x，y，）=（x±а，y±1），其中а∈{1，2，3}，y，y，∈{0，1}。根据σ 的定义，有σ（v）=（x±а+2（y±1））8。假设σ（u）=σ（v），则（x+2y）8=（x±а+2y±2）8，即（±а±2）8=0，这与0≤|±а±2|≤5 矛盾。因此，σ（u）≠σ（v），即σ 是P2·Pn的一个3- 距离染色。

定理2.2 对任意的整数m≥3，有（1）χ3（Pm·P2）=6；（2）χ3（Pm·P3）=9。

证明（1）P3·Pm中任意两个顶点之间的距离不超过3，且顶点数等于6，所以）χ3（P3·P2）=6。由于P3·P2包含于Pm·P2，根据引理1.1 可知，χ3（Pm·P2）≥6。为证明χ3（Pm·P2）≤6，现仅需用6 种颜色构造一个Pm·P2的3- 距离染色。对x=0，1，y=0，1，…，m-1，令σ（x，y）=（2x+y）6。显然，σ 所用颜色集为{0，1，2，…，5}。

现在验证σ 是Pm·P2的3- 距离染色。在Pm·P2中取任意一个顶点u=（x，y），那么与之任意距离不超过3 的顶点可能为v=（x，，y，）=（x，y±β）或v=（x，，y，）=（x±1，y±а），其中β∈{1，2}，а∈{1，2，3}.根据σ 的定义有σ（v）=（2x+y±β）6或σ（v）=（2（x±1）+y±β）6，假设σ（u）=σ（v），则

（2x+y）6=（2x+y±β）6或（2x+y）6=（2（x±1）+y+а）6

即（±β）=0 或（±2±а）=0，这是不可能的，因为与1≤|±β|≤2，0≤|±2±а|≤5 矛盾。因此，σ（u）≠σ（v），即σ 是Pm·P2的一个3- 距离染色。

（2）P3·P3中任意两顶点之间的距离不超过3，且顶点数等于9，所以χ3（P3·P3）=9。因P3·P3包含于Pm·P3，由引理1.1 可知，χ3（Pm·P3）≥9。为证明χ3（Pm·P3）≤9，仅需用9 种颜色构造一个Pm·P3的3- 距离染色。对x=0，1，2 y=0，1…，m-1，令σ（x，y）=（3x+y）9。显然，σ 所用的颜色集为{0，1，2，…，8}。

现在验证σ 是Pm·P3的3- 距离染色。在Pm·P3中取任意两个顶点u=（x，y）和v=（x'，y'），使得1≤dG（u，v）≤3，其中x，x'，∈{0，1，2}。假设σ（u）=σ（v），可推出矛盾。事实上，根据半强积的定义，有（x'，y'）=（x，y±β）或（x'，y'）=（x±1，y±а），或（x'，y'）=（x±2，y±γ），其中β∈{1，2}，а∈{0，1，2，3}，γ∈{0，1，2}。由σ 的定义有

σ（x'，y'）=（3x+y±β）9，或σ（x'，y'）=（3（x±1）+y±а）9。

或σ（x'，y'）=（3（x±2）+y±γ）9。

若σ（x'，y'）=（3x+y±β）9，因σ（u）=σ（v），则（3x+y）9=（3x+y±β）9，即（±β）9=0，这与1≤|±β|≤2 矛盾。若σ（x'，y'）=（3（x±1）+y±а）9，因σ（u）=σ（v），则（3x+y）9=（3（x±1）+y±а）9，即（±3±а）9=0，这与0≤|±3±а|≤6 矛盾。若σ（x'，y'）=（3（x±2）+y±γ）9，因σ（u）=σ（v），则（3x+y）9=（3（x±2）+y±γ）9，即（±6±γ）9=0，这与4≤|±6±γ|≤8 矛盾。

由以上分析可知，σ（u）≠σ（v）。因此，σ 是Pm·P3的一个3-距离染色。

定理2.3 对任意整数m≥3 与n≥4，有χ3（Pm·Pn）=12。

证明记G=Pm·Pn，设B3={（x，y）|x=0，1，2，3，y=0，1，2}。显然B3中任意两个顶点的距离不超过3，且|B|=12，所以χ3（G）≥12。为证明χ3（G）≤12，仅需用12 种颜色构造一个G的3- 距离染色。

对x=0，1，…，n-1，y=0，1，…，m-1，令σ（x，y）=（x+2y）12。显然，σ 所用颜色集为{0，1，2，…，11}。

现在验证σ 是G 的3- 距离染色。在G 中任取两个顶点u=（x，y）和v=（x'，y'），使得1≤d（u，v）≤3。假设σ（u）=σ（v），可推出矛盾。事实上，由σ 的定义可知，σ（u）=（x+2y）12。

当d（u，v）=1 时，有（x'，y'）=（x±1，y）或（x'，y'）=（x±1，y±1），因σ（u）=σ（v），则（x+2y）12=（x±1+2y）12或（x+2y）12=（x±1+2（y±1））12，即（±1）12=0 或（±1±2）12=0，这是不可能的，因为与1≤|±1±2|≤3 矛盾。

当d（u，v）=2 时，有（x'，y'）=（x±2，y±а）或（x'，y'）=（x，y±β），其中β∈{1，2}，а∈{0，1，2}。因σ（u）=σ（v），则（x+2y）12=（x±2+2（y±а））12或（x+2y）12=（x±2+2（y±β））12，即（±2±2а）12=0 或（±2β）12=0。这是不可能的，因为1≤|±2±2а|≤6，2≤|±2β|≤4。

当d（u，v）=3 时，有（x'，y'）=（x±3，y±а）或（x'，y'）=（x±1，y±β），其中β∈{2，3}，а∈{0，1，2，3}。因σ（u）=σ（v），则（x+2y）12=（x±3+2（y±а））12或（x+2y）12=（x±1+2（y±β））12，即（±3±2а）12=0 或（±1±2β）12=0。这是不可能的，因为1≤|±3±2а|≤9，3≤|±1±2β|≤7。

由以上分析可知，σ（u）≠σ（v）。因此，σ 是G的一个3- 距离染色。

关于路的强积的3- 距离染色，有以下定理2.4- 定理2.6。

顶点（x，0）及距离不超过3 的可能邻点为

（x，0），（x，1），（x±1，0），（x±2，0），（x±3，0），（x±1，1），（x±2，1），（x±3，1）

根据σ 的定义，（x，0）及其距离不超过3 的可能邻点的颜色为

σ（x，0）=（x）8，σ（x，1）=（x+2）8

σ（x±1，0）=（x±1）8，σ（x±2，0）=（x±2）8

σ（x±3，0）=（x±3）8，σ（x±1，1）=（x±1+2）8

σ（x±2，1）=（x±2+2）8，σ（x±3，1）=（x±3+2）8

易见，点（x，0）及其距离不超过3 的邻点具有不同的颜色，否

则可推出矛盾：存在一个数i∈{1，2，3，4，5}，使得（i）8=0。顶点（x，1）及距离不超过3 的可能邻点为

（x，1），（x，0），（x±1，1），（x±2，1），（x±3，1），（x±1，0），（x±2，0），（x±3，0）