＊ 兩類3－正則圖的鄰點可區(qū)別I－全染色

楊隨義，楊曉亞，唐保祥，何萬生

（天水師范學院 數(shù)學與統(tǒng)計學院，甘肅 天水 741001）

＊兩類3－正則圖的鄰點可區(qū)別I－全染色

楊隨義，楊曉亞，唐保祥，何萬生

（天水師范學院 數(shù)學與統(tǒng)計學院，甘肅 天水 741001）

圖G的I－全染色是指若干種顏色對圖G的頂點和邊的一個分配，使得任意兩個相鄰的點的顏色不同，任意兩條相鄰的邊的顏色不同.在圖G的一個I－全染色下，G的任意一個點的色集合是指該點的顏色以及與該點相關(guān)聯(lián)的全體邊的顏色構(gòu)成的集合.圖G的一個I－全染色稱為是鄰點可區(qū)別的，如果任意兩個相鄰點的色集合不相等.對一個圖G進行鄰點可區(qū)別I－全染色所用的最少顏色的數(shù)目稱為圖G的鄰點可區(qū)別I－全色數(shù).本文給出了兩類3－正則圖的鄰點可區(qū)別I－全色數(shù).

I－全染色；鄰點可區(qū)別I－全染色；鄰點可區(qū)別I－全色數(shù)

圖的染色是圖論的重要研究內(nèi)容之一，由計算機科學和信息科學等所產(chǎn)生的點可區(qū)別邊染色［1］，鄰點可區(qū)別邊染色（或鄰強邊染色）［2］，及鄰點可區(qū)別全染色［3－6］等都是十分困難的問題，至今文獻甚少.在此基礎(chǔ)上，進一步提出了圖的新染色概念.圖的鄰點可區(qū)別I－全染色是其中之一［7］，本文給出了兩類3－正則圖的鄰點可區(qū)別I－全色數(shù).

定義1.1［6］設(shè)G是階至少為2的連通圖，k為正整數(shù)，f是圖G的使用顏色為1，2，…，k的正常全染色.對?x∈V（G），令C（x）表示在f下點x的顏色及與x關(guān)聯(lián)的全體邊的顏色構(gòu)成的集合，稱之為在全染色f下點x的色集合，令ˉC（x）＝｛1，2，…，k｝＼C（x）.如果?uv∈E（G），有C（u）≠C（v），則f稱為G的k－鄰點可區(qū)別全染色.稱

為G的鄰點可區(qū)別全色數(shù).

定義1.2［7］設(shè)G是階至少為2的連通圖，f是圖G的使用顏色為1，2，…，k的全染色.如果G的任意相鄰的點染不同的顏色，并且G的任意相鄰的邊染不同的顏色，那么稱f為G的I－全染色.設(shè)f是G的I－全染色，對?x∈V（G），令C（x）表示在f下點x的顏色及與x關(guān)聯(lián)的全體邊的顏色構(gòu)成的集合，稱之為在f下點x的色集合，令ˉC（x）＝｛1，2，…，k｝＼C（x）.如果對?uv∈E（G），有C（u）≠C（v），則f稱為G的k－鄰點可區(qū)別I－全染色（簡記為k－AVDIT染色）.稱

為G的鄰點可區(qū)別I－全色數(shù).

定義1.3 設(shè)k，m均為正整數(shù)，圖Bk，m的定義如下：

定義1.4 設(shè)k，m均為正整數(shù)，且k≥3，圖Rk，m的定義如下：

圖1 B 4，2Fig.1 B 4，2

圖2 R 4，3Fig.2 R4，3

本文給出了圖Bk，m和R k，m的鄰點可區(qū)別I－全色數(shù).

在本文的主要定理的證明中，為了方便將“邊ui，ju i＋1，2j－1和ui，ju i＋1，2j分別用顏色a和b去染色”寫為“有序邊對［ui，ju i＋1，2j－1，ui，ju i＋1，2j］用［a，b］去染”；

將“點ui＋1，2j－1和ui＋1，2j分別用顏色a和b去染色”寫為“有序點對［ui＋1，2j－1，ui＋1，2j］用［a，b］去染”；對多于兩條的邊構(gòu)成的有序組及多于兩個的點構(gòu)成的有序組，有類似的說法和記號.

圖中未加說明的術(shù)語，記號可參看文獻［8］.

1 主要結(jié)果

引理1.1［7］對簡單圖G，則有

（1）對?x∈V（K4），都有｜ˉC（x）｜＝1，由此可知，f（x）∈S（x）＝C（x），其中，S（x）表示在f下與x關(guān)聯(lián)的全體邊的顏色構(gòu)成的集合，此時考慮f在E（K4）上的限制g，則g是K4的一個點可區(qū)別正常邊染色，由參考文獻［2］知χ′as（K4）＝5，顯然矛盾.

（2）存在x∈V（K4），使得｜ˉC（x）｜＝0，即C（x）＝｛1，2，3，4｝，不妨設(shè)C（v0.1）＝｛1，2，3，4｝且f（v0，1）＝1，則對于u1，1，u1，2，u1，3一定有｜C（u1，1）｜＝｜C（u1，2）｜＝｜C（u1，3）｜＝3，進而可知，f（u1，j）∈S（u1，j）＝C（u1，j）（j∈｛1，2，3｝）.

下面根據(jù)ˉC（u1，1），ˉC（u1，2），ˉC（u1，3）三者中有沒有等于｛1｝分兩種情形討論：

①若ˉC（u1，1），ˉC（u1，2），ˉC（u1，3）三者中存在一個等于｛1｝，不妨設(shè)ˉC（u1，1）＝｛1｝，即C（u1，1）＝｛2，3，4｝.若f（v0，1，u1，1）＝2，則邊u1，1u1，2和u1，1u1，3只能分別用3，4或4，3去染，這就有C（u1，2）＝｛3，4，f（u1，2u1，3）｝，C（u1，3）＝｛3，4，f（u1，2u1，3）｝，由此可知，C（u1，2）＝C（u1，3）；對于f（u0，1u1，1）＝3或f（v0，1u1，1）＝4可得類似結(jié)果，這顯然與f是K4的鄰點可區(qū)別I－全染色矛盾.

②若ˉC（u1，1），ˉC（u1，2），ˉC（u1，3）三者均不等于｛1｝，則ˉC（u1，1），ˉC（u1，2），ˉC（u1，3）兩兩互不相等且只能分別?。?｝，｛3｝，｛4｝中的某一個，此時，考慮f下在E（K4）上的即制g，則g是K4的一個點可區(qū)別正常邊染色，又與χ′as（K4）＝5矛盾，綜上所述可知，χi at（K4）＝χi

at（B1，1）＞4.

2）證明（B1，1）＝5.下面給出B1，1有一個5－AVDIT染色.定義一個從V（B1，1）∪E（B1，1）到｛1，2，3，4，5｝的映射f如下：f（v0，1）＝4，f（u1，j）＝j(luò)，f（v0，1u1，j）＝j(luò)，j∈｛1，2，3｝.f（u1，1u1，2）＝4，f（u1，2，u1，3）＝5，f（u1，1u1，3）＝2.在該染色下，有C（v0，1）＝｛1，2，3，4｝，C（u1，1）＝｛1，2，4｝，C（u1，2）＝｛2，4，5｝，C（u1，3）＝｛2，3，5｝.可看出，任意相鄰兩點的色集合不同.所以，f是3－正則圖B1，1的一個5－AVDIT染色.

情形2 當k≥2且m＝1時，欲證明（Bk，1）＝4，僅需給出圖Bk，1的一個4－AVDIT染色，如下構(gòu)造Bk，1的一個使用顏色1，2，3，4的I－全染色f：

點v0，t（t∈｛1，2，…，k｝）用顏色2（當t≡1（mod2）時）或3（當t≡0（mod2）時）去染；

對于t∈｛1，2，…，k－1｝，有序三邊組［v0，tu1，3t－2，v0，tu1，3t－1，v0，tu1，3t］和有序三點組［u1，3t－2，u1，3t－1，u1，3t］均用［4，1，3］（當t≡1（mod2）時）或［1，4，2］（當t≡0（mod2）時）去染；

有序三邊組［v0，ku1，3k－2，v0，ku1，3k－1，u0，k u1，3k］和有序三點組［u1，3k－2，u1，3k－1，u1，3k］均用［4，3，1］（當k≡1（mod2）時）或［1，4，2］（當k≡0（mod2）時）去染；

對于t∈｛1，2，…，k－1｝，有序三邊 組［u1，3t－2u1，3t－1，u1，3t－1u1，3t，u1，3t u1，3（t＋1）－2］均用［3，2，4］（當t≡1（mod2）時）或［2，3，1］（當t≡0（mod2）時）去染；

有序三邊組［u1，3k－2u1，3k－1，u1，3k－1u1，3k，u1，3tu1，1］用［2，4，2］（當k≡1（mod2））或［2，3，1］（當k≡0（mod2）時）去染.

在上述染色下，C（v0，t）＝｛1，2，3，4｝，t∈｛1，2，…，k｝.

對于t∈｛2，…，k－1｝，當t≡1（mod2）時，C（u1，3t－2），C（u1，3t－1），C（u1，3t）分別為｛1，3，4｝，｛1，2，3｝，｛2，3，4｝；當t≡0（mod2）時，C（u1，3t－2），C（u1，3t－1），C（u1，3t）分別為｛1，2，4｝，｛2，3，4｝，｛1，2，3｝.

當k≡1（mod2）時，C（u1，1），C（u1，2），C（u1，3），C（u1，3k－2），C（u1，3k－1），C（u1，3k）分別為｛2，3，4｝，｛1，2，3｝｛2，3，4｝，｛1，2，4｝，｛2，3，4｝，｛1，2，4｝，

當k≡0（mod2）時，C（u1，1），C（u1，2），C（u1，3），C（u1，3k－2），C（u1，3k－1），C（u1，3k）分別為｛1，3，4｝，｛1，2，3｝，｛2，3，4｝，｛1，2，4｝，｛2，3，4｝，｛1，2，3｝.

可看出，任意相鄰兩點的色集合不同.所以，f是3－正則圖B k，1的一個4－AVDIT染色.

情形3 當m≥2時，欲證明χi at（Bk，m）＝4，僅需給出圖Bk，m的一個4－AVDIT染色.

在圖Bk，m中與點v0，t的距離不超過m的所有點導出的子圖記為∑t（t∈｛1，2，…，k｝），顯然，∑t?∑l（1≤t＜l≤k），該同構(gòu)使得點v0，t與v0，l對應(yīng)，點ui，j與u i，s對應(yīng)，其中2i－1·3（t－1）＋1≤j≤2i－1·3t，2i－1·3（l－1）＋1≤s≤2i－1·3l且s－j＝2i－1·3（l－t）（i∈｛1，2，…，m｝），滿足上述條件的∑t到∑l的同構(gòu)是唯一的，因此，對于圖Bk，m包含的每一個∑t（t∈｛1，2，…，k｝），利用前面所建立的同構(gòu)關(guān)系可得∑t?∑1（2≤t≤k），于是讓∑t（t∈｛2，3，…，k｝）與∑1的染色相同（即∑t與∑1對應(yīng)的邊染同色，對應(yīng)的點染同色），最后將未被染色的k條邊均用1（若m≡0（mod2）時）或2（若m≡1（mod2）時）去染，這樣得到Bk，m的一個染色記為f.

下面只需對∑1進行鄰點可區(qū)別I－全染色，具體染色方法如下：

點v0，1用顏色2去染，

對有序三邊組［v0，1u1，1，v0，1u1，2，v0，1u1，3］和有序點對［u1，1，u1，2，u1，3］均用［4，1，3］去染.

對于i∈｛1，2，…，m－1｝，j∈｛1，2，…，2i｝，有序邊對［ui，ju i＋1，2j－1，ui，ju i＋1，2j］和有序點對［ui＋1，2j－1ui＋1，2j］均用［2，3］（若i≡1（mod2）時）或［1，4］（若i≡0（mod2）時）去染；

對于i∈｛1，2，…，m－1｝，j∈ ｛2i＋1，…，2i－1·3｝，有序邊對 ［ui，j u i＋1，2j－1，ui，j u i＋1，2j］和 有 序點對［ui＋1，2j－1ui＋1，2j］均用［2，4］（若i≡1（mod2）時）或［1，3］（若i≡0（mod2）時）去染.

對于j∈｛1，2，…，2m｝且j≡1（mod2），有序邊對［um，ju m，j＋1，um，j＋1um，j＋2］用［3，2］（若m≡1（mod2）時）或［4，1］（若m≡0（mod2））；

對于j∈｛2m＋1，…，2m－1·3｝且j≡1（mod2），有序邊對［um，j u m，j＋1，um，j＋1um，j＋2］用［4，2］（若m≡1（mod2）時）或［3，1］（若m≡0（mod2）時）去染，最后將邊um，3·2m－1um，3·2m－1＋1的色去掉.

下面只需說明∑1中任兩個相鄰點在f下的色集合不同.顯然有C（v0，1）＝｛1，2，3，4｝，C（v1，1），C（u1，2），C（u1，3），分別為｛2，3，4｝，｛1，2，3｝，｛2，3，4｝，其余各點ui，j（i∈｛2，3，…，m｝）的色集合為

特別地，當m≡1（mod2）時，C（um，1）＝｛1，2，3｝，C（um，2m－1），C（um，2·2m－1），C（um，3·2m－1）均為｛2，3，4｝；當m≡0（mod2）時，C（um，1）＝｛1，2，4｝，C（um，2m－1），C（um，2·2m－1），C（um，3·2m－1）均為｛1，3，4｝，可看到，任意相鄰兩點的色集合不同.所以，f是3－正則圖B k，m的一個4－AVDIT染色.

定理1.2 對于3－正則圖R k，m，則有χi at（Rk，m）＝4.

證明 易知Δ（Rk，m）＝3，由引理1.1知，χi at（Rk，m）≥4，欲證明χiat（Rk，m）＝4，僅需給出圖Rk，m的一個4－AVDIT染色的.下面分兩種情形進行證明.

情形1 當m＝1時.

（1）當k＝3時，將3－正則圖R3，1的染色方法記為R3染法，具體如下：

有序三邊組［v0，1v0，2，v0，2v0，3，v0，3v0，1］和有序三點組［v0，1，v0，2，v0，3］均用［1，2，3］去染；

有序三邊組［u1，1u1，2，u1，2u1，3，u1，3u1，1］和有序三點組［u1，1，u1，2，u1，3］均用［2，3，1］去染；剩余的邊均用4去染.

在上述染色之下，

C（v0，1），C（v0，2），C（v0，3）分別為：｛1，3，4｝，｛1，2，4｝，｛2，3，4｝；

C（u1，1），C（u1，2），C（u1，3）分別為：｛1，2，4｝，｛2，3，4｝，｛1，3，4｝；可看到，任意相鄰兩點的色集合不同.所以，上述染色是3－正則圖R3，1的一個4－AVDIT染色.

（2）當k＝4時，將3－正則圖R4，1的染色方法記為R4染法，具體如下：

有序四邊組［v0，1v0，2，v0，2v0，3，v0，3v0，4，v0，4v0，1］和有序四點組［v0，1，v0，2，v0，3，v0，4］均用［1，2，4，3］去染；

有序四邊組［u1，1u1，2，u1，2u1，3，u1，3u1，4，u1，4u1，1］和有序四點組［u1，1，u1，2，u1，3，u1，4］均用［2，4，3，1］去染；

有序四邊組［v0，1u1，1，v0，2u1，2，v0，3u1，3，v0，4u1，4］用［4，3，1，2］去染.

在上述染色之下，C（v0，1），C（v0，2），C（v0，3），C（v0，4）分 別 為 ｛1，3，4｝，｛1，2，3｝，｛1，2，4｝，｛2，3，4｝；C（u1，1），C（u1，2），C（u1，3），C（u1，4）分別為：｛1，2，4｝，｛2，3，4｝，｛1，3，4｝，｛1，2，3｝，可看到，任意相鄰兩點的色集合不同.所以，上述染色是3－正則圖R4，1的一個4－AVDIT染色.

（3）當k＝5時，3－正則圖R5，1的染色方法記為R5，具體如下：

有序五邊組［v0，1v0，2，v0，2v0，3，v0，3v0，4，v0，4v0，5，v0，5v0，1］用［4，1，4，2，1］去染；

有序五點組［v0，1，v0，2，v0，3，v0，4，v0，5］用［4，3，4，3，1］去染.

有序五邊組［u1，1u1，2，u1，2u1，3，u1，3u1，4，u1，4u1，5，u1，5u1，1］用［1，4，3，2，4］去染.

有序五點組［u1，1，u1，2，u1，3，u1，4，u1，5］用［3，4，2，1，4］去染；

有序五邊組［v0，1u1，1，v0，2u1，2，v0，3u1，3，v0，4u1，4，v0，5u1，5］用［2，2，2，1，3］去染.

在上述染色之下，C（v0，1），C（v0，2），C（v0，3），C（v0，4），C（v0，5）分別為｛1，2，4｝，｛1，2，3，4｝，｛1，2，4｝，｛1，2，3，4｝，｛1，2，3｝；C（u1，1），C（u1，2），C（u1，3），C（u1，4），C（u1，5）分別為｛1，2，3，4｝，｛1，2，4｝，｛2，3，4｝，｛1，2，3｝，｛2，3，4｝，可看到，任意相鄰兩點的色集合不同.所以，上述染色是3－正則圖R5，1的一個4－AVDIT染色.

（4）當k≥6時，對于3－正則圖R k，1的染色可以將R3染法和R4染法作為工具反復使用，具體如下：

為了說明方法的合理性，我們僅對R4染法與R3染法一次結(jié)合驗證，以R7，1為例.

先用一次R4染法：有序四邊組［v0，1v0，2，v0，2v0，3，v0，3v0，4，v0，4v0，5］和有序四點組［v0，1，v0，2，v0，3，v0，4］均用［1，2，4，3］去染；有序四邊組［u1，1u1，2，u1，2u1，3，u1，3u1，4，u1，4u1，5］和有序四點組［u1，1，u1，2，u1，3，u1，4］均用［2，4，3，1］去染；有序四邊組［v0，1u1，1，v0，2u1，2，v0，3u1，3，u0，4v1，4］用［4，3，1，2］去染.

然后用一次R3染去：有序三邊組［v0，5v0，6，v0，6v0，7，v0，7v0，1］和有序三點組［v0，5，v0，6，v0，7］均用［1，2，3］去染；有序三邊組［u1，5u1，6，u1，6u1，7，u1，7u1，1］和有序三點組［u1，5，u1，6，u1，7］均用［2，3，1］去染；剩余的邊均用4去染.

在上述染色之下，C（v0，1），C（v0，2），C（v0，3），C（v0，4），C（v0，5），C（v0，6），C（v0，7）分別為：｛1，2，4｝，｛2，3，4｝，｛1，3，4｝，｛1，2，4｝，｛2，3，4｝，；C（u1，1），C（u1，2），C（u1，3），C（u1，4），C（u1，5），C（U1，6），C（u1，7）分別為：｛1，2，4｝，｛2，3，4｝，｛1，3，4｝，｛1，2，3｝，｛1，2，4｝，｛2，3，4｝，｛1，3，4｝.可看到，任意相鄰兩點的色集合不同，說明對3－正則圖R k，1的這種染色方法是合理的，進而說明上述染色是3－正則圖R k，1的一個4－AVDIT染色.

情形2 當m≥2時.

在圖Rk，m中與點v0t（此時暫不考慮v0，t與其它v0，l之間的邊）的距離不超過m－1的所有點導出的子圖記為∑t（t∈｛1，2，…，k｝），顯然∑t?∑p（1≤t＜p≤k），該同構(gòu)使得點v0，t與v0，p對應(yīng)，點ui，j與u i，s對應(yīng)，其中2i－1·（t－1）＋1≤j≤2i－1·t，2i－1·（p－1）＋1≤s≤2i－1·p且s－j＝2i－1·（p－t）（i∈｛1，2，…，m｝）.滿足上述條件的∑t到∑p的同構(gòu)是唯一的，因此，對于圖Rk，m包含的每一個∑t（t∈｛1，2，…，k｝），利用前面所建立的同構(gòu)關(guān)系可得∑t?∑p（1≤t＜p≤k），于是當t≡1（mod2）（t∈｛3，4，…，k－1｝）讓∑t與∑1的染色相同（即∑t與∑2對應(yīng)的邊染同色，對應(yīng)的點染同色）；當t≡0（mod2）（t∈｛3，4，…，k－1｝）讓∑t與∑2的染色相同（即∑t與∑2對應(yīng)的邊染同色，對應(yīng)的點染同色）；對∑k來說，當k≡0（mod2）時與∑2的染色相同，當k≡1（mod2）時，∑k的單獨染色.

下面只需對∑1，∑2，∑k（若k≡1（mod2）時）進行鄰點可區(qū)別I－全染色.

第一步，對∑1染色.

點v0，1用顏色1去染，邊v0，1u1，1和點u1，1均用顏色4去染；

對于i∈｛1，2，…，m－1｝，j∈｛1，2，…，2i－1｝，有序邊對［ui，j u i＋1，2j－1，ui，j u i＋1，2j］和有序點對［ui，1，2j－1，ui＋1，2j］均用［2，3］（若i≡1（mod2）時）或［1，4］（若i≡0（mod2）時）去染；

對于j∈｛1，2，…，2m－1｝且j≡1（mod2），有序邊對［um，ju m，j＋1，um，j＋1um，j＋2］用［3，2］（若m≡1（mod2）時）或［4，1］（若m≡0（mod2）），最后將邊um，2m－1um，2m－1＋1的色去掉.

特別地，當k≡1（mod2）且m＝2時，將點u2，1的顏色2換成顏色1.

第二步，對∑2染色.

點v0，2用顏色2去染，邊v0，2u1，2和點u1，2均用顏色3去染；

對于i∈｛1，2，…，m－1｝，j∈｛2i－1＋1，…，2i－1·2｝，有序邊對［ui，j u i＋1，2j－1，ui，j u i＋1，2j］和有序點對［ui＋1，2j－1，ui＋1，2j］均用［2，4］（若i≡1（mod2）時）或［1，3］（若i≡0（mod2）時）去染；

對于j∈｛2m－1＋1，…，2m－1·2｝且j≡1（mod2），有序邊對［um，j u m，j＋1，um，j＋1um，j＋2］用［4，2］（若m≡1（mod2）時）或［3，1］（若m≡0（mod2）），最后將邊um，2·2m－1um，2·2m－1＋1的色去掉.

第三步，對∑k（當k≡1（mod2）時）染色.

點v0，k用顏色3去染，邊v0，ku1，k和點u1，k均用顏色4去染；

對于i∈｛1，2，…，m－1｝，j∈｛2i－1·（k－1）＋1，…，2i－1·k｝，有序邊對［ui，ju i＋1，2j－1，ui，ju i＋1，2j］和有序點對［ui＋1，2j－1，ui＋1，2j］均用［2，1］（若i≡1（mod2）時）或［3，4］（若i≡0（mod2）時）去染；

對于j∈｛（k－1）·2m－1＋1，…，k·2m－1｝且j≡1（mod2），有序邊對［um，ju m，j＋1，um，j＋1um，j＋2］用［1，2］（若m≡1（mod2）時）或［4，3］（若m≡0（mod2）），最后將邊um，k·2m－1um，1的色去掉.

特別地，當m＝2時，將點u1，k的顏色4換成顏色2，將點u2，2k－1的顏色2換成顏色3，將點u2，2k的顏色1換成顏色4；當m≡1（mod2）（m≥3）時，將點um，（k－1）·2m－1＋1的顏色3換成顏色1.

對邊v0，tv0，t＋1（t∈｛1，2，3，…，k－1｝）用顏色1（當t≡1（mod2）時）或2（當t≡0（mod2）時）去染；

對邊v0，kv0，1用顏色3（當k≡1（mod2）時）或2（當k≡0（mod2）時）去染；

最后將未被染色的k條邊均用2（若m≡1（mod2）時）或1（若m≡0（mod2）時）去染，特別地，當k≡1（mod2）且m≡0（mod2）時，將邊um，k·2m－1um，1的色換成3，將圖Rk，m的這一個染色記為f.

下面只需說明∑1，∑2，∑k（當k≡1（mod2）時）中任兩個相鄰點在f下的色集合不同，

在上述染色下，有

特別地，當m＝2時C（u2，2k－1）＝｛1，2，3，4｝；當m≡0（mod2）（m≥3）時C（um，（k－1）·2m－1＋1＝｛1，2，4｝.可看出，任意相鄰兩點的色集合不同，所以，上述染色f是3－正則圖R k，m的一個4－AVDIT染色.

［1］ Fravaron O，Li H，Schelp R H.Strong Edge Colorings of Graphs［J］.DiscreteMathematics，1996，159（1－3）：103－109.

［2］ Zhang Zhong－fu，Liu Lin－zhong，Wang Jian－fang.Adjacent Strong Edge Coloring of Graphs［J］.AppliedMathematicaLetters，2002，15：623－626.

［3］ Cheng Xiang－en，Zhang Zhong－fu，Yan Jing－zhi，etal.Adjacent－vertex－Distinguishing Total Chromatics Numbers onM ycielski’sGraphs of Several Kinds of Particular Graphs［J］.JournalofLanzhouuniversity（NaturalScience），2005，41（2）：117－122.

［4］ 陳祥恩.關(guān)于圖r K2∨Ks的鄰點可區(qū)別全色數(shù)［J］.蘭州大學學報：自然科學版，2007，43（5）：91－93.

［5］ 陳祥恩，張忠輔.關(guān)于圖K2n＋1－E（2K2）的鄰點可區(qū)別全色數(shù)［J］.蘭州大學學報：自然科學版，2005，41（6）：102－105.

［6］ 楊隨義，王治文.一類3－正則圖的關(guān)聯(lián)鄰點可區(qū)別全染色［J］.山西大學學報：自然科學版，2010，33（3）：354－357.

［7］ Zhang Zhong－fu，Woodall D R，Yao Bing，etal.Adjacent Vertex－distinguishing I－total Coloring of Graphs［EB／OL］.（2008－06－12）http：／／202.201／18.40：8080／mas5／.

［8］ Bondy J A，Murty U S R.Graph Theory［M］.London：Springer，2008.

Adjacent Vertex－distinguishing I－total Coloring of Two Kinds of 3－regular Graphs

YANG Sui－yi，YANG Xiao－ya，TANG Bao－xiang，HE Wan－sheng
（DepartmentofMathematics，TianshuiNormalUniversity，Tianshui741001，China）

The I－total coloring of a graphsGis an assignment of some colors to its vertices and edges such that no two adjacent vertices receive the dame color and no two adjacent edges receive the same color.Under the I－total coloring ofG，the color set of a vertexxofGis the set of all colors which are assigned to vertexxor the edges incident tox.An I－total coloring is called adjacent vertex distinguishing if any two adjacent vertices have different color sets.The minimum number of colors required in an adjacent vertex－distinguishing I－total coloring is called adjacent vertex－distinguishing I－total chromatic number.The adjacent vertex－distinguishing I－total coloring of two kind of 3－regular graphs are discussed.

I－total coloring；adjacent vertex－distinguishing I－total coloring；adjacent vertexdistinguishing I－total chromatic number

O157.5

A

2011－04－19；

2011－06－10

甘肅省自然科學基金（096RJZE106）；天水師范學院中青年教師科研資助項目（TSA1102）

楊隨義（1977－），男，甘肅天水人，碩士，副教授，研究方向：代數(shù)圖論與染色.E－mail：yangzhangyike＠yahoo.com.cn

0253－2395（2012）04－0641－07

book=647,ebook=349