三條路的笛卡爾乘積圖的L（1，2）-標(biāo)號(hào)數(shù)

饒威麗，吳 瓊，李 瑩

（天津職業(yè)技術(shù)師范大學(xué)理學(xué)院，天津 300222）

當(dāng)今世界，隨著計(jì)算機(jī)無(wú)線網(wǎng)絡(luò)的迅猛發(fā)展，網(wǎng)絡(luò)代碼資源日漸緊缺，因此對(duì)有限的無(wú)線網(wǎng)絡(luò)代碼資源進(jìn)行合理優(yōu)化分配顯得尤為重要。在計(jì)算機(jī)無(wú)線網(wǎng)絡(luò)中，如果2 個(gè)站點(diǎn)距離“非常近”，則存在直接干擾，為了避免直接干擾，要求站點(diǎn)的代碼不同，假設(shè)差異為j；而如果2 個(gè)站點(diǎn)距離“比較近”且與同一個(gè)站點(diǎn)距離“非常近”，則存在間接干擾，而這樣距離較近的站點(diǎn)之間為了避免直接干擾，同時(shí)也要避免間接干擾，就要求這2 個(gè)站點(diǎn)的代碼差異更大，假設(shè)差異為k，則有j≤k?；谶@些條件，代碼分配問(wèn)題可抽象為圖的L（j，k）-標(biāo)號(hào)問(wèn)題，它不同于無(wú)線電的頻率分配問(wèn)題概括出來(lái)的 L（j，k）-標(biāo)號(hào)問(wèn)題，這里 j≤k。在20 世紀(jì) 90 年代，Bertossi 等[1]闡述了一種模型，只要求距離較近的站點(diǎn)發(fā)射不同的代碼，而忽略站點(diǎn)間的直接干擾，可概括為L(zhǎng)（0，1）-標(biāo)號(hào)問(wèn)題。但在實(shí)際問(wèn)題中，無(wú)論直接干擾還是間接干擾，都需要進(jìn)行規(guī)避，所以在2005 年，Jin 等[2]提出了基于代碼分配問(wèn)題的L（j，k）-標(biāo)號(hào)問(wèn)題。到目前為止，基于代碼分配問(wèn)題的圖的L（j，k）-標(biāo)號(hào)問(wèn)題的研究成果并不多，相關(guān)結(jié)論主要有：2007 年，牛慶杰[3]確定了路、圈和輪的 L（j，k）-標(biāo)號(hào)數(shù)；在文獻(xiàn)[4]中，作者確定了樹和完全圖的2 類乘積圖的 L（j，k）-圓標(biāo)號(hào)數(shù)；2013 年，Shiu 等[5]得到了路和圈 Direct 乘積圖的 L（j，k）-標(biāo)號(hào)數(shù)；Wu 等[6]確定了路和圈 Direct 乘積圖的 L（j，k）-圓標(biāo)號(hào)數(shù)并在文獻(xiàn)[7]中給出了路和圈笛卡爾乘積圖的L（j，k）-標(biāo)號(hào)數(shù)；另外，Wu 等[8-9]分別給出了路的平方的 L（j，k）-圓標(biāo)號(hào)數(shù)以及 L（j，k）-標(biāo)號(hào)數(shù)；2018 年，文獻(xiàn)[10-11]給出了廣義彼得森圖以及 Cactus 圖的 L（j，k）-標(biāo)號(hào)數(shù)，這里的j≤k。隨著無(wú)線網(wǎng)絡(luò)的不斷發(fā)展，人們居住環(huán)境的日益密集，解決二維平面圖的代碼分配問(wèn)題已不能緩解目前代碼匱乏的問(wèn)題。而作為刻畫三維無(wú)線網(wǎng)絡(luò)的最重要的圖——三條路的笛卡爾乘積圖，關(guān)于它的研究就顯得尤為重要了。本文確定了任意長(zhǎng)度的三條路的笛卡爾乘積圖的L（1，2）-標(biāo)號(hào)數(shù)，給出了相應(yīng)圖的最優(yōu)標(biāo)號(hào)方案，可直接被利用到三維無(wú)線網(wǎng)絡(luò)的代碼分配問(wèn)題中，從而達(dá)到節(jié)約資源，提高經(jīng)濟(jì)效益的目的。

1 基本定義

定義1[11]標(biāo)號(hào)問(wèn)題的定義如下

設(shè)f 為一個(gè)從圖G 的頂點(diǎn)集到非負(fù)整數(shù)集的映射，若符合條件

f 便為圖 G 的一個(gè) L（1，2）-標(biāo)號(hào)。圖 G 的 L（1，2）-標(biāo)號(hào)數(shù)用λ1，2（G）表示，標(biāo)號(hào)的最大值與最小值之間的差稱為標(biāo)號(hào)的跨度，而所有標(biāo)號(hào)中最小的跨度則稱為圖 G 的 L（1，2）-標(biāo)號(hào)數(shù)。

定義2設(shè)A、B、C 為集合，用A 中元素為第一元素，B 中元素為第二元素，C 中元素為第三元素構(gòu)成有序組，所有這樣的有序組組成的集合叫做集合A、B、C的笛卡爾積，記作A×B×C，即

A×B×C={（u，v，w）|u∈A∧v∈B∧w∈C}

定義3圖G、圖H 和圖K 的笛卡爾乘積圖是一個(gè)空間圖，記為G?H?K，其頂點(diǎn)集合為V（G）×V（H）×V（K），頂點(diǎn)（u，v，w）和頂點(diǎn)（u′，v′，w′）相鄰當(dāng)且僅當(dāng)（1）u=u′，v=v′且 ww′∈E（K）或者（2）u=u′，w=w′且 vv′∈E（H）或者（3）v=v′，w=w′且 uu′∈E（G）。

定義4[12]設(shè)G（V，E）是無(wú)向圖，圖G 中的一個(gè)頂點(diǎn)和邊交替出現(xiàn)的非空序列P=v0e1v1e2…ekvk稱為圖G 的一條由頂點(diǎn) v0到頂點(diǎn) vk的路。其中 v0，v1，…，vk是圖 G 的頂點(diǎn)，e1，e2，…，ek是圖 G 的邊。

定義 5圖 Pl?Pm?Pn的頂點(diǎn)記為 va，b，c，其中 0≤a≤l-1，0≤b≤m-1，0≤c≤n-1 。為了方便敘述，把頂點(diǎn) v0，0，0放在三維直角坐標(biāo)系的原點(diǎn)，而頂點(diǎn) va，b，c對(duì)應(yīng)于空間直角坐標(biāo)系中點(diǎn)（a，b，c）。

定義6設(shè)區(qū)間[M，N]，區(qū)間長(zhǎng)度定義為N - M，記作|[M，N]|=N-M。

本文中涉及的其他相關(guān)概念請(qǐng)參閱文獻(xiàn)[13]。

2 笛卡爾乘積圖的 L（1，2）-標(biāo)號(hào)數(shù)

引理1[4]令圖H 是圖G 的一個(gè)導(dǎo)出子圖，則λ1，2（G）≥λ1，2（H）。

引理2[7]令 A、B、n 為正實(shí)數(shù)，有|[A]n- [B]n| =

引理 3令 A、B、n 為正實(shí)數(shù)，且 0≤A ＜ n，有[A+

證明

（1）若 0≤A+B ＜ n，0≤B ＜ n，即[A+B]n-[B]n=A+B-B=A。

（2）若 n≤A+B ＜ 2n，0≤B ＜ n，即[A+B]n-[B]n=A+B-n-B=A-n。

（3）若 B≥n，B=r+kn，kn≤B≤（k+1）n，kn≤A+B≤（k+2）n。

2.1 圖P2?Pm?Pn的 L（1，2）-標(biāo)號(hào)數(shù)

本節(jié)先討論特殊情形 P2?Pm?Pn的 L（1，2）-標(biāo)號(hào)數(shù)。

定理1λ1，2（P2?P2?P2）=6。

證明一方面，給圖 P2?P2?P2一個(gè)標(biāo)號(hào) f 如下

f（v0，0，0）= f（v1，1，1）= 0；f（v0，1，0）= f（v1，0，1）= 2；

f（v1，0，0）=f（v0，1，1）=4；f（v1，1，0）=f（v0，0，1）=6。

不難驗(yàn)證，f 是圖 P2?P2?P2的一個(gè) L（1，2）-標(biāo)號(hào)且跨度為6，即λ1，2（P2?P2?P2）≤6。

另一方面，因 v0，0，0、v1，0，1、v0，1，1、v1，1，0是互相距離為2 的4 個(gè)頂點(diǎn)，根據(jù)L（1，2）-標(biāo)號(hào)的定義知λ1，2（P2?P2?P2）≥6 。

綜上可得，λ1，2（P2?P2?P2）=6。

引理4設(shè)圖H1如圖1 所示，λ1，2（H1）=7。

圖1 圖H1

證明一方面，定義f 是圖H1的一個(gè)標(biāo)號(hào)，標(biāo)號(hào)f如下

f（v0）=0；f（v1）=2；f（v2）=4；f（v3）=6；

f（u0）= 1；f（u1）=3；f（u2）=5；f（u3）=7。

不難驗(yàn)證，f 滿足 L（1，2）-標(biāo)號(hào)條件且跨度為 7，即λ1，2（H1）≤7。

另一方面，假設(shè)λ1，2（H1）＜7，令f 是圖H1的一個(gè)L（1，2）-標(biāo)號(hào)且其中標(biāo)號(hào)子區(qū)間In=[n，n +1），n=0，1，…，6 。因?yàn)轫旤c(diǎn) v0、v1、v2、v3相互之間距離為2，則它們的標(biāo)號(hào)相互之間至少差2，即它們的標(biāo)號(hào)應(yīng)落在 I0∪I2∪I4∪I6中。又因?yàn)轫旤c(diǎn) u1與 v0、v1、v2、v3這 4 個(gè)頂點(diǎn)都相鄰，且標(biāo)號(hào)子區(qū)間 I0、I2、I4、I6的長(zhǎng)度均小于1，故f（u1）∈I1∪I3∪I5。又因頂點(diǎn)u0、u1、u2、u3相互之間距離為2。若f（u1）∈Ii，則

f（u0），f（u2），f（u3）∈[0，i - 1）∪[i + 2，7），其中i =1，3，5。

（1）若f（u1）∈I1∪I5，則f（u0），f（u2），f（u3）∈[3，7），或f（u0），f（u2），f（u3）∈[0，4）。因?yàn)閒（u0），f（u2），f（u3）中任意2 個(gè)標(biāo)號(hào)至少差2，所以它們最大標(biāo)號(hào)和最小標(biāo)號(hào)之間的差至少為 4，而區(qū)間[3，7）或[0，4）的長(zhǎng)度小于 4，所以矛盾。

（2） 若 f（u1）∈I3，則 f（u0），f（u2），f（u3）∈[0，2）∪[5，7）。因?yàn)閒（u0）、f（u2）、f（u3）中任意2 個(gè)標(biāo)號(hào)至少差2，而區(qū)間[0，2）∪[5，7）的長(zhǎng)度都小于 2，所以它們一共至多包含f（u0）、f（u2）、f（u3）中2 個(gè)標(biāo)號(hào)，所以矛盾。故λ1，2（H1）≥7。

綜上所述，λ1，2（H1）=7。

定理2若n∈N 且n≥3，則λ1，2（P2?P2?Pn）=7。

證明一方面，給圖P2?P2?Pn定義一個(gè)標(biāo)號(hào) f 為

f（v0，y，0）=[5[y]4]8；f（v0，y，1）=[3（[y]4+1）]8；

f（v1，y，0）=[3（[y+2]4+1）]8；f（v1，y，1）=[5[y+2]4]8。

這里的 0≤y≤n-1，如圖 P2?P2?P8的一個(gè) 7-L（1，2）-標(biāo)號(hào)如圖 2 所示。不難驗(yàn)證 f 滿足 L（1，2）-標(biāo)號(hào)的條件，且跨度為7，即當(dāng)n≥3 時(shí)，λ1，2（P2?P2?Pn）≤7。

圖 2 圖 P2?P2?P8 的一個(gè) 7-L（1，2）-標(biāo)號(hào)

另一方面，由引理4 可知λ1，2（H1）=7，又因圖H1是圖 P2?P2?Pn的一個(gè)導(dǎo)出子圖，由引理 1 可知，λ1，2（P2?P2?Pn）≥λ1，2（H1）=7，這里的n≥3。

綜上可得，當(dāng)n≥3 時(shí)，λ1，2（P2?P2?Pn）=7。

引理5設(shè)圖H2如圖3 所示，λ1，2（H2）=9。

圖3 圖H2

證明一方面，定義f 是圖H2的一個(gè)標(biāo)號(hào)，標(biāo)號(hào)f如下

f（v0）=0；f（v1）=2；f（v2）=4；f（v3）=6；f（v4）=8；

f（u0）=1；f（u1）=3；f（u2）=5；f（u3）=7；f（u4）=9。

不難驗(yàn)證，f 滿足 L（1，2）-標(biāo)號(hào)條件且跨度為 9，即λ1，2（H2）≤9。

另一方面，假設(shè)λ1，2（H2）＜9，令f 是圖H2的一個(gè)L（1，2）-標(biāo)號(hào)且其中標(biāo)號(hào)子區(qū)間In=[n，n+1），n=0，1，…，8。因?yàn)轫旤c(diǎn) v0、v1、v2、v3、v4相互之間距離為2，則它們的標(biāo)號(hào)相互之間至少差2，即它們的標(biāo)號(hào)應(yīng)落在 I0∪I2∪I4∪I6∪I8中。又因?yàn)轫旤c(diǎn) u0與 v0、v1、v2、v3、v4這 5 個(gè)頂點(diǎn)都相鄰，且標(biāo)號(hào)子區(qū)間 I0、I2、I4、I6、I8的長(zhǎng)度均小于1，故f（u1）∈I1∪I3∪I5∪I7。又因頂點(diǎn) u0、u1、u2、u3、u4相互之間距離為 2，若 f（u1）∈Ii，則f（u0），f（u2），f（u3），f（u4）∈[0，i-1）∪[i+2，9），其中i=1，3，5，7。

（1）若f（u1）∈I1∪I7，則f（u0），f（u2），f（u3），f（u4）∈[3，9），或f（u0），f（u2），f（u3），f（u4）∈[0，6）。因?yàn)閒（u0）、f（u2）、f（u3）、f（u4）中任意2 個(gè)標(biāo)號(hào)至少差2，所以它們的最大標(biāo)號(hào)與最小標(biāo)號(hào)的差至少為6，而區(qū)間[3，9）或[0，6）的長(zhǎng)度小于 6，所以矛盾。

（2）若f（u1）∈I3∪I5，則f（u0），f（u2），f（u3），f（u4）∈[0，2）∪[5，9），或f（u0），f（u2），f（u3），f（u4）∈[0，4）∪[7，9）。

因?yàn)閒（u0）、f（u2）、f（u3）、f（u4）中任意2 個(gè)標(biāo)號(hào)至少差2，而區(qū)間[0，2）或[7，9）的長(zhǎng)度小于2，所以f（u0）、f（u2）、f（u3）、f（u4）中至多只有 1 個(gè)標(biāo)號(hào)落在區(qū)間[0，2）或[7，9）中。又因f（u0）、f（u2）、f（u3）、f（u4）中任意3 個(gè)標(biāo)號(hào)的最大標(biāo)號(hào)與最小標(biāo)號(hào)的差至少為4，而區(qū)間[5，9）或[0，4）的長(zhǎng)度小于4，所以矛盾。故λ1，2（H2）≥9。

綜上可得，λ1，2（H2）=9。

定理3若m，n∈N 且m，n≥3，λ1，2（P2?Pm?Pn）=9。

證明一方面，給圖P2?Pm?Pn定義一個(gè)標(biāo)號(hào)f 如下

式中：x∈{0，1}；0≤y≤m-1；2≤z≤n-1。

驗(yàn)證 f 滿足 L（1，2）-標(biāo)號(hào)的條件：任取 vx，y，z∈V（P2?Pm?Pn），由圖的對(duì)稱性，與vx，y，z相鄰的頂點(diǎn)，只需驗(yàn)證vx，y，z與 vx，y+1，z、v1-x，y，z、vx，y，z+1的標(biāo)號(hào)差至少為 1 即可；與距離為 2 的頂點(diǎn)，只需驗(yàn)證 vx，y，z與 vx，y+2，z、v1-x，y+1，z、v1-x，y，z+1、vx，y+1，z+1、vx，y，z+2的標(biāo)號(hào)差至少為 2 即可。而根據(jù)標(biāo)號(hào)函數(shù)直接可知，在 vx，y+1，z、v1-x，y，z與 vx，y，z的標(biāo)號(hào)差異至少為1，vx，y+2，z與 vx，y，z的標(biāo)號(hào)差異至少為 2。下面利用引理 2和引理3，對(duì)其他標(biāo)號(hào)進(jìn)行驗(yàn)證。

類似地，可驗(yàn)證|f（v1-x，y，z+1）-f（vx，y，z）|≥2，|f（vx，y+1，z+1）-f（vx，y，z）|≥2，這里不再詳細(xì)列出。因此，f 滿足L（1，2）-標(biāo)號(hào)條件且跨度是9，即λ1，2（P2?Pm?Pn）≤9，這里的m，n≥3。

另一方面，由引理5 得λ1，2（H2）=9，又因H2是圖P2?Pm?Pn的一個(gè)導(dǎo)出子圖，由引理1 可知，λ1，2（P2?Pm?Pn）≥λ1，2（H2）=9，這里的m，n≥3。

綜上可得，當(dāng)m，n≥3 時(shí)，λ1，2（P2?Pm?Pn）=9。

2.2 圖Pl?Pm?Pn 的L（1，2）-標(biāo)號(hào)數(shù)

這一節(jié)主要介紹 Pl?Pm?Pn的 L（1，2）-標(biāo)號(hào)數(shù)，這里的 l≥3，m≥3，n≥4。

引理6設(shè)圖H3如圖4 所示，λ1，2（H3）=11。

圖4 圖H3

證明一方面，定義f 是圖H3的一個(gè)標(biāo)號(hào)，標(biāo)號(hào)f如下

f（v0）=0；f（v1）=2；f（v2）=4；

f（v3）=6；f（v4）=8；f（v5）=10；

f（u0）=1；f（u1）=3；f（u2）=5；

f（u3）=7；f（u4）=9；f（u5）=11。

不難驗(yàn)證，f 滿足 L（1，2）-標(biāo)號(hào)條件且跨度為 11，即λ1，2（H3）≤11。

另一方面，假設(shè)λ1，2（H3）＜11。令f 是圖H3的一個(gè) L（1，2）-標(biāo)號(hào)且其中標(biāo)號(hào)子區(qū)間In=[n，n+1），n=0，1，…，10。因?yàn)轫旤c(diǎn) v0、v1、v2、v3、v4、v5相互之間距離為2，則它們的標(biāo)號(hào)相互之間至少差2，即它們的標(biāo)號(hào)應(yīng)落在 I0∪I2∪I4∪I6∪I8∪I10。又因?yàn)轫旤c(diǎn) u1與 v0、v1、v2、v3、v4、v5這 6 個(gè)頂點(diǎn)都相鄰，且標(biāo)號(hào)子區(qū)間I0、I2、I4、I6、I8、I10的長(zhǎng)度均小于1，故f（u1）∈I1∪I3∪I5∪I7∪I9。又因 u0、u1、u2、u3、u4、u5相互之間距離為 2，若f（u1）∈Ii，則f（u0），f（u2），f（u3），f（u4），f（u5）∈[0，i-1）∪[i+2，11），其中 i=1，3，5，7，9。

（1）若 f（u1）∈ I1∪ I9，則 f（u0），f（u2），f（u3），f（u4），f（u5）∈[3，11），或f（u0），f（u2），f（u3），f（u4），f（u5）∈[0，8）。因?yàn)閒（u0）、f（u2）、f（u3）、f（u4）、f（u5）中任意2 個(gè)標(biāo)號(hào)至少差2，所以它們的最大標(biāo)號(hào)與最小標(biāo)號(hào)的差至少為 8，而區(qū)間[3，11）與[0，8）的長(zhǎng)度均小于 8，所以矛盾。

（2）若f（u1）∈I3∪I7，則f（u0），f（u2），f（u3），f（u4），f（u5）∈[0，2）∪[5，11），或f（u0），f（u2），f（u3），f（u4），f（u5）∈[0，6）∪[9，11）。因?yàn)閒（u0）、f（u2）、f（u3）、f（u4）、f（u5）中任意 2 個(gè)標(biāo)號(hào)至少差 2，而區(qū)間[0，2）或[9，11）的長(zhǎng)度小于2，所以至多包含f（u0）、f（u2）、f（u3）、f（u4）、f（u5）中一個(gè)標(biāo)號(hào)。又因f（u0）、f（u2）、f（u3）、f（u4）、f（u5）中任意4 個(gè)標(biāo)號(hào)的最大標(biāo)號(hào)與最小標(biāo)號(hào)的差至少為6，而區(qū)間[5，11）或[0，6）的長(zhǎng)度均小于 6，所以矛盾。

（3）若f（u1）∈I5，則f（u0），f（u2），f（u3），f（u4），f（u5）∈[0，4）∪[7，11）。因?yàn)閒（u0）、f（u2）、f（u3）、f（u4）、f（u5）中任意2 個(gè)標(biāo)號(hào)至少差2，而區(qū)間[0，4）的長(zhǎng)度小于4，所以至多包含2 個(gè)標(biāo)號(hào)。又因f（u0）、f（u2）、f（u3）、f（u4）、f（u5）中任意3 個(gè)標(biāo)號(hào)的最大標(biāo)號(hào)與最小標(biāo)號(hào)的差至少為4，而區(qū)間[7，11）的長(zhǎng)度小于4，所以矛盾。故λ1，2（H3）≥11。

綜上可得，λ1，2（H3）=11。

定理4λ1，2（P3?P3?P3）=10。

證明一方面，給圖 P3?P3?P3一個(gè)標(biāo)號(hào) f 如下

f（v0，0，0）=f（v1，1，2）=0

f（v0，1，0）=f（v1，2，2）=f（v2，0，1）=1

f（v1，2，1）=10

f（v0，2，0）=f（v0，0，2）=f（v2，1，1）=2

f（v0，1，2）=f（v1，0，0）=f（v2，2，1）=3

f（v0，2，2）=f（v1，1，0）=f（v2，0，2）=4

f（v0，0，1）=f（v1，2，0）=f（v2，1，2）=5

f（v0，1，1）=f（v2，0，0）=f（v2，2，1）=6

f（v1，0，2）=f（v0，2，1）=f（v2，1，0）=7

f（v1，0，1）=f（v2，2，0）=8

f（v1，1，1）=9

不難驗(yàn)證，f 是圖 P3?P3?P3的一個(gè) L（1，2）-標(biāo)號(hào)且跨度為10，即λ1，2（P3?P3?P3）≤10。

另一方面，因圖 P3?P3?P3中 v1，1，2、v1，2，1、v2，1，1、v1，0，1、v0，1，1、v1，1，0是 6 個(gè)互相距離為 2 的頂點(diǎn)，根據(jù) L（1，2）-標(biāo)號(hào)的定義知，λ1，2（P3?P3?P3）≥10。綜上可得，λ1，2（P3?P3?P3）=10。

定理5若l，m，n∈N 且l≥3，m≥3，n≥4，λ1，2（Pl?Pm?Pn）=11。

證明一方面，定義 f 是圖 Pl?Pm?Pn的一個(gè)標(biāo)號(hào)，標(biāo)號(hào)f 如下

f（vx，y，z）=[3x+y+5z]12

式中：0≤x≤l-1；0≤y≤m-1；0≤z≤n-1。

驗(yàn)證f（vx，y，z）=[3x+y+5z]12滿足L（1，2）-標(biāo)號(hào)的條件：任取 vx，y，z∈V（Pl?Pm?Pn），由圖的對(duì)稱性，與 vx，y，z相鄰的頂點(diǎn)，只需驗(yàn)證 vx，y，z與 vx，y+1，z、vx，y，z+1、vx+1，y，z的標(biāo)號(hào)差至少為 1 即可；與 vx，y，z距離為 2 的頂點(diǎn)，只需驗(yàn)證的標(biāo)號(hào)差至少為2 即可。

（1）驗(yàn)證|f（vx，y+1，z）-f（vx，y，z）|≥1 如下

（2）驗(yàn)證|f（vx，y+2，z）-f（vx，y，z）|≥2 如下

類似地，可利用引理3 對(duì)其他點(diǎn)標(biāo)號(hào)進(jìn)行驗(yàn)證f 滿足L（1，2）-標(biāo)號(hào)條件且最大跨度是11，即λ1，2（Pl?Pm?Pn）≤11，這里的 l≥3，m≥3，n≥4。

另一方面，由引理6 可知λ1，2（H3）= 11，又因H3是圖Pl?Pm?Pn的一個(gè)導(dǎo)出子圖，由引理1 可知λ1，2（Pl?Pm?Pn）≥λ1，2（H3）=11，這里的l≥3，m≥3，n≥4。

綜上可得，當(dāng)l≥3，m≥3，n≥4 時(shí)，λ1，2（Pl?Pm?Pn）=11。

3 結(jié) 論

本文針對(duì)三條路的笛卡爾乘積圖L（1，2）-標(biāo)號(hào)數(shù)展開(kāi)研究，得出所有長(zhǎng)度的三條路的笛卡爾乘積圖的L（1，2）-標(biāo)號(hào)數(shù)如下