顧忠棟，強(qiáng)會(huì)英，魏邦魁

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

兩類特殊圖的鄰點(diǎn)強(qiáng)可區(qū)別E-全染色

顧忠棟，強(qiáng)會(huì)英*，魏邦魁

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

對(duì)簡(jiǎn)單圖G（V，E），存在一個(gè)正整數(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的鄰點(diǎn)強(qiáng)可區(qū)別E-全染色，且稱最小的數(shù)k為圖G的鄰點(diǎn)強(qiáng)可區(qū)別E-全色數(shù)。在此基礎(chǔ)上應(yīng)用構(gòu)造染色法研究了圖Fm×Fn、M（Pn2）的鄰點(diǎn)強(qiáng)可區(qū)別E-全染色，并得出了其鄰點(diǎn)強(qiáng)可區(qū)別E-全色數(shù)。

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

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

1　基本概念

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

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

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

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

則稱f為圖G的k-鄰點(diǎn)強(qiáng)可區(qū)別全染色，簡(jiǎn)記為k-AVSDTC，又稱

為G的鄰點(diǎn)強(qiáng)可區(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）對(duì)任意的uv∈E（G），u≠v，f（u）≠f（v），f（u）≠f（uv）；

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

則稱f為G的k－鄰點(diǎn)強(qiáng)可區(qū)別E－全染色，簡(jiǎn)記為k－E－AVSDTC，又稱

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

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

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

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

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

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

2　主要結(jié)論

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

此時(shí)對(duì)f的色集合如下：

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

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

證明設(shè)圖 M（Pn2）的頂點(diǎn)集和邊集分別為 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可知先證明否則若事實(shí)上因圖存在三圈，易證故下面給出圖M（Pn2）的一個(gè)5-E-AVSDTC染色法，令f如下：

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

此時(shí)對(duì)f色集合如下：

顯然，對(duì)?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］張忠輔，程輝，姚兵，等.圖的鄰點(diǎn)強(qiáng)可區(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］程輝，謝雁.圖的鄰點(diǎn)強(qiáng)可區(qū)別VI-全染色［J］.蘭州大學(xué)學(xué)報(bào)，2010，46（6）：97-101.

［9］王倩，田雙亮.幾類笛卡爾直積圖的鄰點(diǎn)可區(qū)別全染色［J］.蘇州科技學(xué)院學(xué)報(bào)（自然科學(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圖的鄰點(diǎn)強(qiáng)邊色數(shù)和鄰點(diǎn)可區(qū)別全染色［J］.廣西科學(xué)，2008，15（1）：4-6.

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

［13］馬剛，張忠輔.路與輪連圖的鄰強(qiáng)邊色數(shù)［J］.蘇州科技學(xué)院學(xué)報(bào)（自然科學(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é)基金資助項(xiàng)目（61262045）

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