兩類特殊圖的鄰點強可區(qū)別E-全染色

顧忠棟，強會英，魏邦魁

（蘭州交通大學(xué) 數(shù)理與軟件工程學(xué)院，甘肅 蘭州730070）

兩類特殊圖的鄰點強可區(qū)別E-全染色

顧忠棟，強會英*，魏邦魁

（蘭州交通大學(xué) 數(shù)理與軟件工程學(xué)院，甘肅 蘭州730070）

對簡單圖G（V，E），存在一個正整數(shù)k，使得映射f：V（G）∪E（G）→｛1，2，…，k｝，如果?uv∈E（G），有f（u）≠f（v），f（u）≠f（uv）且C（u）≠C（v），其中C（u）=｛f（u）｝∪｛f（uv），f（v）|uv∈E（G），v∈V（G）｝，則稱f是圖G的鄰點強可區(qū)別E-全染色，且稱最小的數(shù)k為圖G的鄰點強可區(qū)別E-全色數(shù)。在此基礎(chǔ)上應(yīng)用構(gòu)造染色法研究了圖Fm×Fn、M（Pn2）的鄰點強可區(qū)別E-全染色，并得出了其鄰點強可區(qū)別E-全色數(shù)。

笛卡爾積圖；k方圖；鄰點強可區(qū)別E-全染色；鄰點強可區(qū)別E-全色數(shù)

隨著計算機的飛速發(fā)展，信息化和數(shù)字化技術(shù)的不斷進步，許多實際問題的數(shù)學(xué)模型使離散型結(jié)構(gòu)上的數(shù)字化技術(shù)得到了更多人的關(guān)注，圖的染色理論［1］作為離散數(shù)學(xué)的一個重要的組成部分，自然得到了快速發(fā)展，因此，受到了國際數(shù)學(xué)界與工程界越來越廣泛的重視。Noga Alon在2002年數(shù)學(xué)國際大會上作了“離散數(shù)學(xué)方法與挑戰(zhàn)”的大會報告后，圖的染色成為一個很活躍、很新穎的研究領(lǐng)域。1993年，A.C.Burris在他的博士論文中提到了點可區(qū)別正常邊染色（也稱強邊染色）的概念［2］，此后P.N.Balister等人［3］對該問題進行了深入的討論，許多研究成果都在國際權(quán)威雜志上刊出。在無線通訊網(wǎng)絡(luò)中，為了防止網(wǎng)絡(luò)中不同的長點之間信號頻率的共振，必須保證不同站點之間擁有不同的通訊頻率，為了解決無線傳感器網(wǎng)絡(luò)中相鄰點通信沖突問題及交通運輸中危險品運輸?shù)呐渌驼{(diào)度安全問題等，張忠輔教授首次提出了鄰點可區(qū)別正常邊染色［4］的概念，這一問題與點可區(qū)別邊染色的研究具有相同的難度，因此，國內(nèi)外專家對此問題作了大量研究。2004年，張忠輔教授在鄰點可區(qū)別正常邊染色的基礎(chǔ)上提出了鄰點可區(qū)別全染色［5］的概念。2007年，張忠輔教授又提出了鄰點強可區(qū)別全染色的概念［6］。2010年，程輝等在鄰點強可區(qū)別的基礎(chǔ)上提出了鄰點強可區(qū)別EI-全染色［7］和鄰點強可區(qū)別VI-全染色的概念［8］。筆者在此基礎(chǔ)上得到了兩類特殊圖的鄰點強可區(qū)別E-全染色。下面給出相關(guān)的定義。

1　基本概念

定義1［6］設(shè)圖G是階數(shù)至少為2的連通圖，映射f：V（G）∪E（G）→｛1，2，…，k｝，其中k為正整數(shù)，如果f滿足：

（1）對任意的uv∈E（G），f（u）≠f（v），f（u）≠f（uv），f（v）≠f（uv）；

（2）對任意的uv，uw∈E（G），u≠w，f（uv）≠f（uw）；

（3）對任意的uv∈E（G），u≠v，C（u）≠C（v）。

則稱f為圖G的k-鄰點強可區(qū)別全染色，簡記為k-AVSDTC，又稱

為G的鄰點強可區(qū)別全色數(shù)，這里C（u）=｛f（u）｝∪｛f（uv），f（v）|uv∈E（G），v∈V（G）｝。

定義2設(shè)圖G是階數(shù)至少為2的連通圖，映射f：V（G）∪E（G）→｛1，2，…，k｝，其中k為自然數(shù)，如果f滿足：

（1）對任意的uv∈E（G），u≠v，f（u）≠f（v），f（u）≠f（uv）；

（2）對任意的uv∈E（G），u≠v，C（u）≠C（v）。

則稱f為G的k－鄰點強可區(qū)別E－全染色，簡記為k－E－AVSDTC，又稱

為圖的鄰點強可區(qū)別E－全色數(shù)。這里C（u）＝｛f（u）｝∪｛f（uv），f（v）|uv∈E（G），v∈V（G）｝。

由圖的鄰點強可區(qū)別全染色和圖的鄰點強可區(qū)別E-全染色的概念，下面引理成立：

定義3［9］設(shè)m階扇Fm和n階扇Fn，即Fm與Fn構(gòu)成的笛卡爾直積圖Fm×Fn的定義為

定義4［10］對圖G＝（V，E），和自然數(shù)k，若V（Gk）＝V（G），E（Gk）＝E（G）∪｛uv|d（u，v）=k｝，則稱圖Gk為圖G的k方圖。

定義5［11］對圖G（V，E），M（G）稱為圖G的Mycielski圖，其中：

文中未加說明的術(shù)語可參考文獻［12-13］。

2　主要結(jié)論

定理1對于扇和扇的笛卡爾積圖Fm×Fn（m≥3，n≥3），則有

此時對f的色集合如下：

顯然，對?uv∈E（G），有C（u）≠C（v），故結(jié)論成立。

定理2設(shè)Pn是n個點的路（n≥4）則，有

證明設(shè)圖 M（Pn2）的頂點集和邊集分別為 V（M（Pn2））＝｛ui|i=1，2，…，n｝∪｛vj|j=1，2，…，n｝∪｛w｝，E（M（Pn2））＝E（Pn2）∪｛uivj|uivj∈E（Pn2），1≤i，j≤n｝∪｛wvj|1≤j≤n｝。易知 χ（M（Pn2））＝3，由引理 1可知先證明否則若事實上因圖存在三圈，易證故下面給出圖M（Pn2）的一個5-E-AVSDTC染色法，令f如下：

當(dāng)i＝3時，f（u3vj）＝5；當(dāng)i≡2（mod 3）時，f（uivj）＝5，j=1，2，…，n；

此時對f色集合如下：

顯然，對?uv∈M（Pn2），有C（u）≠C（v）。結(jié)論成立。

［1］BONDY J A，MARTY U S R.Graph Theory with Application［M］.New York：The Macmillan Press Ltd，1976.

［2］BURRIS A C，SCHELP R H.Vertex-distinguishing proper edge-coloring［J］.J of Graph Theory，1997，26（2）：73-82.

［3］BALISTER P N，PIORDAN O M，SCHELP R H.Vertex-distinguishing edge coloring of graph［J］.Graph Throry，2003，42（2）：95-109.

［4］ZHANG Zhongfu，LIU Linzhong，WANG Jianfang.Adjacent strong edge-coloring of graph［J］.Applied Mathematic Letter，2002，15（5）：623-626.

［5］ZHANG Zhongfu，CHEN Xiangen，LI Jingwen，et al.On adjacent vertex-distinguishing total coloring of graphs［J］.Science in China：Ser A Mathmatics，2005，48（3）：289-299.

［6］張忠輔，程輝，姚兵，等.圖的鄰點強可區(qū)別全染色［J］.中國科學(xué)（A輯：數(shù)學(xué)），2007，37（9）：1073-1082.

［7］CHENG Hui，WANG Zhiyong.Adjacent vertex strongly distinguishing EI-total coloring of graphs［J］.Shandong Univ Nat Sci，2010（3）：289-299.

［8］程輝，謝雁.圖的鄰點強可區(qū)別VI-全染色［J］.蘭州大學(xué)學(xué)報，2010，46（6）：97-101.

［9］王倩，田雙亮.幾類笛卡爾直積圖的鄰點可區(qū)別全染色［J］.蘇州科技學(xué)院學(xué)報（自然科學(xué)版），2010，27（4）：15-17.

［10］FAVARON O，LI H，SCHELP R H.Strong edge coloring of graphs［J］.Discret Mathematics，1996，1（3）：103-109.

［11］孔令峰，蘇文龍，羅海鵬，等.pn2的Mycielski圖的鄰點強邊色數(shù)和鄰點可區(qū)別全染色［J］.廣西科學(xué)，2008，15（1）：4-6.

［12］強會英，王洪申.圖的鄰點強可區(qū)別全色數(shù)的一個上界［J］.數(shù)學(xué)進展，2013，42（6）：801-805.

［13］馬剛，張忠輔.路與輪連圖的鄰強邊色數(shù)［J］.蘇州科技學(xué)院學(xué)報（自然科學(xué)版），2007，24（2）：1-4.

責(zé)任編輯：謝金春

On the adaject vertex strongly distinguishing E-total coloring of two special graphs

GU Zhongdong，QIANG Huiying，WEI Bangkui
（College of Mathematics，Physics and Software Engineering，Lanzhou Jiaotong University，Lanzhou 730070，China）

Let G（V，E）be a simple graph，k be a positive integer，f is a mapping from V（G）∪E（G）to｛1，2，…，k｝，then f is called the adgacent vertex strongly distinguishing E-total coloring of G and the minimum number of k is called the adjacent vertex strongly distinguishing E-total chromatic of G，if?uv∈E（G）f（u）≠f（v），f（u）≠f（uv），?uv∈E（G），C（u）≠C（v）.Based on this，this paper studied the adjacent vertex strongly distinguishing E-total coloring of graph of Fm×Fnand M（pn2）with the structure staining method.And the adjacent vertex strongly distinguishing E-total chromatic numbers of both graphs were obtained thereby.

Cartesian graph；k-square graph；adjacent vertex strongly distinguishing E-total coloring；adjacent vertex strongly distinguishing E-total chromatic number

O157.5MR（2000）Subject Classification：05C15；05C22；05C40

A

1672-0687（2016）03-0018-04

2016-01-16

國家自然科學(xué)基金資助項目（61262045）

顧忠棟（1990-），男，甘肅武威人，碩士研究生，研究方向：圖論與組合優(yōu)化。*通信聯(lián)系人：強會英（1968-），女，甘肅白銀人，教授，碩士生導(dǎo)師，E-mail：qhy2005ww@126.com。