路的積圖的3- 距離染色

代青昂毛

（ 西北民族大學(xué)數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院，甘肅 蘭州730030）

1 概述

圖的距離染色是由F. Kramer 與H. Kramer 于1969 年首次在文獻(xiàn)[1]中提出的，后來在文獻(xiàn)[2]中被表述為k- 距離染色。所謂圖的k- 距離染色是指圖中距離不超過k 的頂點(diǎn)染不同顏色的點(diǎn)染色，其中k 為正整數(shù). 為了研究圖G的k- 距離染色數(shù)，Kramer 等人在文獻(xiàn)[3]中定義了圖G 的k- 方圖，得到了圖G 的k- 方圖距離色數(shù)與k- 距離色數(shù)相等的結(jié)論。關(guān)于圖的積圖的距離染色，Kim 在文獻(xiàn)[4] 中研究m階路Pm與n 階圈Cn 的直積Pm×Cn的2- 距離染色，證明了Pm×Cn的2- 距離染色數(shù)等于5 或6。Kim在文獻(xiàn)[5]中研究了圈的笛卡爾積的2- 距離染色。Fertin 等在文獻(xiàn)[6]中得到了路的笛卡爾積的k- 距離色數(shù)。

本文研究路的半強(qiáng)積與強(qiáng)積的3- 距離染色。圖的半強(qiáng)積與強(qiáng)積的定義具體如下：

定義1.1[7]設(shè)有G 和H 兩個簡單圖，圖G 和H 的半強(qiáng)積G·H有頂點(diǎn)集V（G·H）=V（G）×V（H），任意兩個頂點(diǎn)（u1，v1）與（u2，v2）相鄰當(dāng)且僅當(dāng)u1u2∈E（G）且v1v2∈E（H），或者u1=u2且v1v2∈E（H）。

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

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

2 主要結(jié)論及其證明

設(shè)Pm=u0u1…um-1與Pn=v0v1…vn-1分別為m≥2 階和n≥2 階路。為了方便在直角坐標(biāo)系中研究，把頂點(diǎn)（uy，vx）記為（x，y），其中x=0，1，…，n-1，y=0，1，…，m-1。記（x）k=x（mod k），其中x為整數(shù)。

關(guān)于路的半強(qiáng)積的3- 距離染色，有以下定理2.1- 定理2.3。

定理2.1 對任意的整數(shù)n≥4，有χ3（P2·Pn）=8。

證明P2·P4中任意兩點(diǎn)之間的距離不超過3，并且頂點(diǎn)數(shù)等于8，所以χ3（P2·Pn）=8。由于P2·P4包含于P2·Pn，根據(jù)引理1.1 可知，χ3（P2·Pn）≥8。為證明χ3（P2·Pn）≤8，僅需用8 種顏色構(gòu)造一個P2·Pn的3- 距離染色。對x=0，1，…，n-1，y=0，1，令σ（x，y）=（x+2y）8。顯然，σ 所用顏色集為{0，1，2，…，7}。

現(xiàn)在證明σ 是P2·Pn的3- 距離染色。在P2·Pm中取任意頂點(diǎn)u=（x，y），那么與之任意距離不超過3 的頂點(diǎn)可能為v（x，y，）=（x±а，y±1），其中а∈{1，2，3}，y，y，∈{0，1}。根據(jù)σ 的定義，有σ（v）=（x±а+2（y±1））8。假設(shè)σ（u）=σ（v），則（x+2y）8=（x±а+2y±2）8，即（±а±2）8=0，這與0≤|±а±2|≤5 矛盾。因此，σ（u）≠σ（v），即σ 是P2·Pn的一個3- 距離染色。

定理2.2 對任意的整數(shù)m≥3，有（1）χ3（Pm·P2）=6；（2）χ3（Pm·P3）=9。

證明（1）P3·Pm中任意兩個頂點(diǎn)之間的距離不超過3，且頂點(diǎn)數(shù)等于6，所以）χ3（P3·P2）=6。由于P3·P2包含于Pm·P2，根據(jù)引理1.1 可知，χ3（Pm·P2）≥6。為證明χ3（Pm·P2）≤6，現(xiàn)僅需用6 種顏色構(gòu)造一個Pm·P2的3- 距離染色。對x=0，1，y=0，1，…，m-1，令σ（x，y）=（2x+y）6。顯然，σ 所用顏色集為{0，1，2，…，5}。

現(xiàn)在驗證σ 是Pm·P2的3- 距離染色。在Pm·P2中取任意一個頂點(diǎn)u=（x，y），那么與之任意距離不超過3 的頂點(diǎn)可能為v=（x，，y，）=（x，y±β）或v=（x，，y，）=（x±1，y±а），其中β∈{1，2}，а∈{1，2，3}.根據(jù)σ 的定義有σ（v）=（2x+y±β）6或σ（v）=（2（x±1）+y±β）6，假設(shè)σ（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中任意兩頂點(diǎn)之間的距離不超過3，且頂點(diǎn)數(shù)等于9，所以χ3（P3·P3）=9。因P3·P3包含于Pm·P3，由引理1.1 可知，χ3（Pm·P3）≥9。為證明χ3（Pm·P3）≤9，僅需用9 種顏色構(gòu)造一個Pm·P3的3- 距離染色。對x=0，1，2 y=0，1…，m-1，令σ（x，y）=（3x+y）9。顯然，σ 所用的顏色集為{0，1，2，…，8}。

現(xiàn)在驗證σ 是Pm·P3的3- 距離染色。在Pm·P3中取任意兩個頂點(diǎn)u=（x，y）和v=（x'，y'），使得1≤dG（u，v）≤3，其中x，x'，∈{0，1，2}。假設(shè)σ（u）=σ（v），可推出矛盾。事實上，根據(jù)半強(qiáng)積的定義，有（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 對任意整數(shù)m≥3 與n≥4，有χ3（Pm·Pn）=12。

證明 記G=Pm·Pn，設(shè)B3={（x，y）|x=0，1，2，3，y=0，1，2}。顯然B3中任意兩個頂點(diǎn)的距離不超過3，且|B|=12，所以χ3（G）≥12。為證明χ3（G）≤12，僅需用12 種顏色構(gòu)造一個G的3- 距離染色。

對x=0，1，…，n-1，y=0，1，…，m-1，令σ（x，y）=（x+2y）12。顯然，σ 所用顏色集為{0，1，2，…，11}。

現(xiàn)在驗證σ 是G 的3- 距離染色。在G 中任取兩個頂點(diǎn)u=（x，y）和v=（x'，y'），使得1≤d（u，v）≤3。假設(shè)σ（u）=σ（v），可推出矛盾。事實上，由σ 的定義可知，σ（u）=（x+2y）12。

當(dāng)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āng)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āng)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- 距離染色。

關(guān)于路的強(qiáng)積的3- 距離染色，有以下定理2.4- 定理2.6。

頂點(diǎn)（x，0）及距離不超過3 的可能鄰點(diǎn)為

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

根據(jù)σ 的定義，（x，0）及其距離不超過3 的可能鄰點(diǎn)的顏色為

σ（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

易見，點(diǎn)（x，0）及其距離不超過3 的鄰點(diǎn)具有不同的顏色，否

則可推出矛盾： 存在一個數(shù)i∈{1，2，3，4，5}，使得（i）8=0。頂點(diǎn)（x，1）及距離不超過3 的可能鄰點(diǎn)為

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

根據(jù)σ 的定義，（x，1）及其距離不超過3 的可能鄰點(diǎn)的顏色為

σ（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

由此可知，點(diǎn)（x，1）及其距離不超過3 的鄰點(diǎn)具有不同的顏色，否則推出矛盾： 存在一個數(shù)i∈{1，2，3，4，5}，使得（i）8=0。

對x=0，1，…，n-1，y=0，1，…，m-1，令σ（x，y）=（x+3y）16。顯然，σ 所用顏色集為{0，1，2，…，15}。

現(xiàn)在驗證σ 是G 的3- 距離染色。在G 中任取兩個頂點(diǎn)u=（x，y）和v=（x'，y'），使得1≤d（u，v）≤3。假設(shè)σ（u）=σ（v），可推出矛盾。具體分以下三種情況討論。

情況1 d（u，v）=1。則x'=x±1 且y，={y±β|β∈0，1}，或x'=x且y'=y±1。 根據(jù)σ 的定義有

σ（v）∈{（x±1+3y）16，（x±1+3y±3）16，（x+3y±3）16}.

當(dāng)σ（v）=（x±1+3y）16時，因σ（u）=σ（v），則（x+3y）16=（x±1+3y）16。由此可推出矛盾（±1）16=0。

當(dāng)σ（v）=（x±1+3y±3）16時，因σ（u）=σ（v），則（x+3y）16=（x±1+3y±3）16。

由此可推出矛盾（±1±3）16=0。

當(dāng)σ（v）=（x+3y±3）16時，因σ（u）=σ（v），則（x+3y）16=（x+3y±3）16。由此可推出矛盾（±3）16=0。

情況2 d（u，v）=2。則x'=x±2 且y'={y±β|β∈0，1，2}，或x'={x±а|а∈0，1}且y，=y±2。根據(jù)σ 的定義有

σ（v）∈{（x+3y±3β±2）16|β∈0，1，2）}∪{（x+3y±а±6）16|а∈0，1}

當(dāng)σ（v）∈{（x+3y±3β±2）16|β∈0，1，2）} 時，因σ（u）=σ（v），則

（x+3y）16=（x+3y±2）16，或（x+3y）16=（x+3y±3±2）16，

或（x+3y）16=（x+3y±6±2）16。

由此可推出矛盾：（±2）16=0，或（±3±2）16=0，或（±6±2）16=0。

當(dāng)σ（v）∈{（x+3y±а±6）16|а∈0，1}時，因σ（u）=σ（v），則

（x+3y）16=（x+3y±1±6）16或（x+3y）16=（x+3y±6）16

由此可推出矛盾：（±6）16=0 或（±1±6）16=0。

情況3 d（u，v）=3。則x'=x±3 且y'= {y±β|β∈0，1，2，3}，或y'=y±3 且x'={x±а|а∈0，1，2}。根據(jù)σ 的定義可知

σ（v）∈{（x+3y±3β±3）16|β∈0，1，2，3）}∪{（x+3y±а±9）16|а∈0，1，2}。

當(dāng)σ（v）∈{（x+3y±3β±3）16|β∈0，1，2，3}時，因σ（u）=σ（v），則

（x+3y）16=（x+3y±3）16，或（x+3y）16=（x+3y±3±3）16，

（x+3y）16=（x+3y±6±3）16，或（x+3y）16=（x+3y±9±3）16。

由此可推出矛盾：（±3）16=0，或（±3±3）16=0，或（±3±6）16=0，或（±9±3）16=0。

當(dāng)σ（v）∈{（x+3y±а±9）16|а∈0，1，2}時，因σ（u）=σ（v），則

（x+3y）16=（x+3y±9）16或（x+3y）16=（x+3y±1±9）16

由此可推出矛盾：（±9）16=0 或（±1±9）16=0 或（±2±9）16=0。由以上分析可知，σ（u）≠σ（v）。因此，σ 是G的一個3- 距離染色。