幾種笛卡爾積圖的集合邊染色

張 明，賈澤樂，李沐春

(1. 蘭州交通大學(xué) 電子與信息工程學(xué)院，蘭州 730070；2. 蘭州交通大學(xué) 應(yīng)用數(shù)學(xué)研究所，蘭州 730070)

1 引言

圖染色是圖論中的一個(gè)重要分支,在電路設(shè)計(jì)、交通運(yùn)輸和網(wǎng)絡(luò)分析等方面都有著非常廣泛的應(yīng)用.圖的染色理論有很多分支，其中包括點(diǎn)染色、邊染色、全染色以及在此基礎(chǔ)上添加其他約束條件所產(chǎn)生的一些特殊染色等.近年來,集合染色已經(jīng)成為學(xué)者們關(guān)注的焦點(diǎn).2009年,Hegde[1]提出了集合染色的概念,即給定圖G的一個(gè)從點(diǎn)集V(G)到集合X中一個(gè)非空子集的映射f,其中X={1,2,…,k},k為正整數(shù),如果滿足對(duì)圖G中任意的兩個(gè)相鄰的點(diǎn)u,v，有f(u)≠f(v)，則稱f是圖G的一個(gè)集合點(diǎn)染色，并將集合X中包含顏色的最小數(shù)目k稱為集合點(diǎn)色數(shù)，記為χS(G).2010年,Boutin等[2]定義了強(qiáng)集合染色的概念,即在滿足集合染色的前提下，邊的顏色是通過與其關(guān)聯(lián)的兩個(gè)頂點(diǎn)做對(duì)稱差，同時(shí)集合X中的非空子集分別只在頂點(diǎn)和邊上表現(xiàn)一次,同時(shí)他們對(duì)路和完全二叉樹進(jìn)行了研究，并得到了這兩類圖的強(qiáng)集合色數(shù)均不超過4.2011年，Balister等[3]通過對(duì)圖進(jìn)行點(diǎn)邊劃分,從而找到了幾類滿足集合染色的特殊圖.王艷麗[4]研究了向日葵圖和風(fēng)車圖的集合色數(shù)并給出了團(tuán)數(shù)是3的平面圖,沒有4圈的平面圖及煙花圖的集合色數(shù)[5].2012年，王艷麗等[6]運(yùn)用結(jié)構(gòu)圖論的方法，給出了集合邊色數(shù)的下界以及圖與其頂點(diǎn)刪除子圖、邊刪除子圖的集合邊色數(shù)的關(guān)系.2013年,王艷麗等[7]運(yùn)用分析的方法證明了路與扇的笛卡爾積圖的集合邊色數(shù)等于圖的最大度,同時(shí)她們猜想:任意圖的笛卡爾積圖的集合邊色數(shù)都等于它的最大度.2019年，楊笑蕊等[8]研究了兩類冠圖的鄰和可區(qū)別全染色.2020年，王鴻杰等[9]應(yīng)用構(gòu)造染色函數(shù)法和色集合分配法研究了圈、路、輪等圖的集合點(diǎn)染色.賈澤樂等[13]得到了廣義-Mycielski圖的集合點(diǎn)色數(shù),并得到了廣義θ-圖的集合邊色數(shù)[14].2021年，賈秀卿等[15]運(yùn)用數(shù)學(xué)歸納法并結(jié)合Hall定理研究了單圈圖的D(2)-點(diǎn)可區(qū)別邊染色，并得到了具體的邊色數(shù).

笛卡爾積圖的染色問題是研究特殊圖染色的一個(gè)重要方向.董秀芳[10]分四種情況對(duì)路與完全圖的笛卡爾積圖進(jìn)行研究,并得到一些有趣的結(jié)果.王君帥等[11]利用函數(shù)構(gòu)造法,研究并確定了由簡單圖構(gòu)成的笛卡爾積圖的強(qiáng)邊色數(shù).

在圖染色研究中,利用染色函數(shù)來確定圖的色數(shù)是目前最主要的工具之一.本文首先引入了集合矩陣,然后利用構(gòu)造染色矩陣的方法給出圈與路、路與路、圈與圈的笛卡爾積圖的集合邊染色及其邊色數(shù).

設(shè)G(V,E)是由頂點(diǎn)集V(G),邊集E(G)組成的簡單連通圖.其中Δ和δ分別表示G的最大度和最小度,d(u)表示點(diǎn)u的度數(shù),n表示頂點(diǎn)的個(gè)數(shù)(階數(shù)).用Pn和Cn分別表示n階的路和n階的圈圖.下面引入兩個(gè)圖的笛卡爾積圖的概念。

定義1[12]設(shè)G和H為簡單連通圖,其頂點(diǎn)集分別為V(G)={v1,v2,…,vm},V(H)={v1,v2,…,vn},則圖G和H的笛卡爾積圖G×H定義如下：

為了直觀了解笛卡爾積的定義,給出P4和P5的笛卡爾積圖(即圖P4×P5),見圖1所示.

此外,結(jié)合圖的邊染色、全染色和鄰點(diǎn)可區(qū)別全染色引入圖的集合邊染色概念,具體如下:

定義2對(duì)于簡單連通圖G,令f是E(G)到集合X中非空子集的一個(gè)映射,其中X={1,2,…,k},k為正整數(shù),如果滿足：

1) 對(duì)?uv,uw∈E(G)且v≠w有f(uv)≠f(uw)；

2) 對(duì)?uv,uw∈E(G)且v≠w有f(uv)∩f(uw)≠?.

則稱f為圖G的一個(gè)集合邊染色,簡記作圖G的k-SEC,并將

記為G的集合邊色數(shù).

圖1 P4×P5Fig.1 Graph P4×P5

2 主要結(jié)論

情況1當(dāng)m≡1(mod 2),n≥2時(shí)

當(dāng)1≤i≤m-1且1≤j≤n時(shí)：

為方便表示,用n個(gè)m×1向量S1,S2,…,Sn所構(gòu)成的集合矩陣S來表示n個(gè)不交圈Cm的3-SEC染色f:

S=(S1S2…Sn)=

最后,得到一個(gè)染色矩陣如下：

(S1X1S2Y1…Sn-2X1Sn-1Y1Sn)

情況2當(dāng)m≡0(mod 2),n≥2時(shí),

當(dāng)1≤i≤m且1≤j≤n時(shí)：

為方便表示,用n個(gè)m×1向量T1,T2,…,Tn所構(gòu)成的集合矩陣T來表示n個(gè)不交圈Cm的3-SEC染色f:

T=(T1T2…Tn)=

最后,得到一個(gè)具體的染色矩陣為：

(T1X2T2Y2…Tn-2X2Tn-1Y2Tn)

綜上所述,結(jié)論成立.

情況1當(dāng)m=n=2時(shí),P2×P2=C4.用集合{1},{1,2}依次循環(huán)對(duì)P2×P2中的邊進(jìn)行染色,于是得到了圖P2×P2的一個(gè)2-SEC染色.

首先給出n條路中每條路Pm的一個(gè)2-SEC染色f,當(dāng)1≤i≤m且1≤j≤n時(shí)：

為了方便表示,用n個(gè)m×1向量U1,U2,…,Un所構(gòu)成的集合矩陣U來表示n條不交路Pm的2-SEC染色f:

U=(U1U2…Un)=

最后,構(gòu)造具體的染色矩陣如下：

(U1X3U2Y3…Un-2X3Un-1Y3Un)

綜上所述,結(jié)論成立.

情況1當(dāng)m,n≡0(mod 2)時(shí),

當(dāng)1≤i≤m且1≤j≤n時(shí),

為方便表示,用n個(gè)m×1向量V1,V2,…,Vn所構(gòu)成的集合矩陣V來表示n個(gè)不交圈Cm的2-SEC染色f.

V=(V1V2…Vn)=

最后,經(jīng)過整理得到具體的染色矩陣為

(V1X4V2Y4…Vn-2X4Vn-1Y4VnZ4)

情況2當(dāng)m≡0(mod 2),n≡1(mod 2)時(shí)

當(dāng)1≤i≤m-1且1≤j≤n時(shí),

為方便表示,用n個(gè)m×1向量R1,R2,…,Rn所構(gòu)成的集合矩陣R來表示n個(gè)不交圈Cm的3-SEC染色f.

R=(R1R2…Rn)=

最后,經(jīng)過整理得到具體的染色矩陣為：

(R1X5R2Y5…Rn-2X5Rn-1Y5RnZ5)

情況3當(dāng)m≡1(mod 2),n≡0(mod 2)時(shí)

當(dāng)1≤i≤m且1≤j≤n時(shí),

為方便表示,用n個(gè)m×1向量P1,P2,…,Pn所構(gòu)成的集合矩陣P來表示n個(gè)不交圈Cm的3-SEC染色f.

P=(P1P2…Pn)=

最后經(jīng)過整理得到具體的染色矩陣為

(P1X6P2Y6…Pn-2X6Pn-1Y6PnZ6)

綜上所述，結(jié)論成立.