劉秀麗

（菏澤學(xué)院 數(shù)學(xué)系，山東 菏澤274015）

圖的染色問題是圖論的主要研究內(nèi)容之一，具有重要的理論意義和現(xiàn)實(shí)意義，因而逐漸成為眾多學(xué)者研究的重要領(lǐng)域之一［1］.全染色問題特別是鄰點(diǎn)可區(qū)別全染色又是染色問題中的難點(diǎn).2004年，張忠輔等［2］提出了鄰點(diǎn)可區(qū)別全染色的概念，這個(gè)染色問題已經(jīng)被廣泛研究［3-5］.在鄰點(diǎn)可區(qū)別全染色概念的基礎(chǔ)上，又提出了圖的鄰點(diǎn)可區(qū)別I-全染色的概念.近年來，一些學(xué)者對(duì)一些特殊圖類的鄰點(diǎn)可區(qū)別I-全染色進(jìn)行了研究［6-11］，本文討論了M（Pn），M（Fn）和M（Sn）圖的鄰點(diǎn)可區(qū)別I-全染色，根據(jù)M（Pn），M（Fn）和M（Sn）圖的特征，給出了一種具體的染色方案，得到了它們的鄰點(diǎn)可區(qū)別I-全色數(shù)，并且滿足猜想.

定義1［9，12］對(duì)于階數(shù)不小于2的連通圖G，f是從V（G）∪E（G）到｛1，2，…，k｝的映射，k是自然數(shù)，如果f滿足：

3）任意uv∈EGu≠v有Cu≠Cv.其中C（u）=｛f（u）｝∪｛f（uv）|uv∈E（G）｝，則稱f是圖G的鄰點(diǎn)可區(qū)別I-全染色（簡記作k-IAVDTC），記χiat（G）=min｛k|G有k-鄰點(diǎn)可區(qū)別I-全染色｝為G的鄰點(diǎn)可區(qū)別I-全色數(shù).

定義2［13-14］設(shè)圖G是簡單圖，構(gòu)造圖M（G），使

引理1［9］對(duì)簡單圖G，有χi≥Δ.如果任意uv∈E（G）且d（u）=d（v）=Δ，則有χiat（G）≥Δ+1.

猜想1［11］對(duì)簡單圖G，則有χiat（G）≤Δ+2.

本文所討論的圖均為簡單、有限圖.文中未加說明的記號(hào)和術(shù)語參見文獻(xiàn)［1，15］.

1 主要結(jié)果及證明

定理1 設(shè)Pn表示階為n（n≥3）的路，則有

證明 1）n=3.

由圖M（P3）的結(jié)構(gòu)知Δ（M（P3））=4，所以由引 理1，有χiat（M（P3））≥4.為 了 證 明χiat（M（P3））=4，只 需 給 出M（F3）的 一 個(gè)4-I-AVDTC.為此，構(gòu)造一個(gè)映射f：V（M（P3））∪E（M（P3））→｛1，2，3，4｝：

此時(shí)

綜上，f是M（P3）的一個(gè)4-I-AVDTC.所以χiat（M（P3））=4.

2）n=4.

由圖M（P4）的結(jié)構(gòu)知Δ（M（P4））=4且最大度點(diǎn)相鄰，所以由引理1，有χiat（M（P4））≥5.為了證明χiat（M（P4））=5，只需給出M（P4）的一個(gè)5-I-AVDTC.為此，構(gòu)造一個(gè)映射f：

此時(shí)

綜上，f是M（P4）的一個(gè)5-I-AVDTC.所以χiat（M（P4））=5.

3）n≥5.

由圖M（Pn）的結(jié)構(gòu)知Δ（M（Pn））=n，所以由引 理1，有χiat（M（Pn））≥n.為 了 證 明只 需 給 出M（Pn）一 個(gè)為此，構(gòu)造一個(gè)映射

此時(shí)

綜上，f是M（Pn）的一個(gè)n-I-AVDTC.所以χiat（M（Pn））=n.

定理2 設(shè)Fn表示階為n+1（n≥3）的扇，則有

證明 1）n=3.

由圖M（F3）的結(jié)構(gòu)知Δ（M（F3））=6且最大度點(diǎn)相鄰，所以由引理1，有χiat（M（F3））≥7.不妨設(shè)為 了 證 明只 需 給 出M（F3）的一個(gè)7-I-AVDTC.為此，構(gòu)造一個(gè)映射f：V（M（F3））∪

綜上，f是M（F3）的一個(gè)7-I-AVDTC.

2）n≥4.

由圖M（Fn）的結(jié)構(gòu)知Δ（M（Fn））=2n，所以由引理1，有χiat（M（Fn））≥2n.不妨設(shè)V（Fn）=為了證明只需給出M（Fn）的一 個(gè)2n-I-AVDTC.為此，構(gòu)造一個(gè)映射f：V（M（Fn））∪E（M（Fn））→｛1，2，…，2n｝：

此時(shí)

綜上，f是M（Fn）的一個(gè)2n-I-AVDTC.所以χiat（M（Fn））=2n.

定理3 設(shè)Sn表示階為n+1（n≥3）的星，則有

證明 由圖M（Sn）的結(jié)構(gòu)知Δ（M（Sn））=2n，所以由引理1，有不妨設(shè)為 了 證 明只 需 給 出M（Sn）一 個(gè)2n-I-AVDTC.為此，構(gòu)造一個(gè)映射

此時(shí)

綜上，f是M（Sn）的一個(gè)2n-I-AVDTC.所以χiat（M（Sn））=2n.

［1］Bondy J A，Murty U S A.Graph theory with apolications［M］.London：Macmillan Press Ltd.，1976.

［2］張忠輔，陳祥恩，李敬文，等.關(guān)于圖的鄰點(diǎn)可區(qū)別全染色［J］.中國科學(xué)（A輯），2004，34（5）：574-583.Zhang Zhongfu，Chen Xiang'en，Li Jingwen，et al.Adjacent vertex distinguishing total coloring of graph［J］.Science in China（Ser.A），2004，34（5）：574-583.（in Chinese）

［3］孫曉玲，杜建偉.一類外平面圖的鄰點(diǎn)可區(qū)別全染色［J］.中北大學(xué)學(xué)報(bào)（自然科學(xué)版），2009，30（1）：1-4.Sun Xiaoling，Du Jianwei.Adjacent vertex distinguishing total coloring of a class of outerplane graphs［J］.Journal of Nouth University of China（Natural Science Edition），2009，30（1）：1-4.（in Chinese）

［4］張芳紅，王治文，陳祥恩.C5∨Kt的鄰點(diǎn)可區(qū)別全色數(shù)［J］.數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2012，42（16）：247-252.Zhang Fanghong，Wang Zhiwen，Chen Xiang'en.Adjacent-vertex-distinguishing total chromatic numbers of C5∨Kt［J］.Mathematics in Practice and Theory，2012，42（16）：247-252.（in Chinese）

［5］楊超，姚兵，王宏宇.復(fù)合交叉圈的鄰點(diǎn)可區(qū)別全色數(shù)［J］.華南師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2014，46（1）：22-26.Yang Chao，Yao Bing，Wang Hongyu.Adjacent-vertex distinguishing total chromatic numbers of compound intersecting cycles［J］.Journal of South China Normal University（Natural Science Edition），2014，46（1）：22-26.（in Chinese）

［6］王治文，楊隨義，文飛.關(guān)于若干倍圖的關(guān)聯(lián)鄰點(diǎn)可區(qū)別全染色［J］.內(nèi)蒙古師范大學(xué)學(xué)報(bào)（自然科學(xué)漢文版），2009，38（6）：643-646.Wang Zhiwen，Yang Suiyi，Wen Fei.On a number of incidence adjacent vertex-distinguishing total coloring of double graphs［J］.Journal of Inner Mongolia Normal University（Natural Science Edition），2009，38（6）：643-646.（in Chinese）

［7］楊隨義，王治文.一類3-正則圖的關(guān)聯(lián)鄰點(diǎn)可區(qū)別全染色［J］.山西大學(xué)學(xué)報(bào)（自然科學(xué)版），2010，33（3）：354-357.Yang Suiyi，Wang Zhiwen.Incidence adjacent vertexdistinguishing total coloring of a kind of 3-regular graph［J］.Journal of Shanxi University（Natural Science Edition），2010，33（3）：354-357.（in Chinese）

［8］盧建立，任鳳霞，馬美琳.項(xiàng)鏈的若干染色問題［J］.科技導(dǎo)報(bào)，2012，30（7）：44-47.Lu Jianli，Ren Fengxia，Ma Meilin.Several coloring problems involving necklace［J］.Science and Technology Review，2012，30（7）：44-47.（in Chinese）

［9］楊曉亞.圖Pn□Cm的鄰點(diǎn)可區(qū)別的I-全染色［J］.純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué)，2012，2（6）：757-764.Yang Xiaoya.Adjacent vertex-distinguishing I-total colorings of Pn□Cm［J］.Pure and Applied Mathematics，2012，2（6）：757-764.（in Chinese）

［10］楊隨義，高毓平，何萬生.圖Pm□Kn的鄰點(diǎn)可區(qū)別I-全染色［J］.數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2013，43（1）：212-218.Yang Suiyi，Gao Yuping，He Wansheng.Adjacent vertex-distinguishing I-total coloring of Pm□Kn［J］.Mathematics in Practice and Theory，2013，43（1）：212-218.（in Chinese）

［11］Chen Xiangen，Gao Yuping，Yao Bing.Not necessarily proper total colourings which are adjacent vertex distinguishing［J］.International Journal of Computer Mathematics，2013，90（11）：2298-2307.

［12］田京京.冠圖Cm·Sn和Cm·Pn的鄰點(diǎn)可區(qū)別的I-全染色［J］.西南師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2013，38（2）：25-28.Tian Jingjing.On adjacent vertex-distinguishing Itotal chromatic number of the crown graph Cm·Snand Cm·Pn［J］.Journal of Southwest China Normal University（Natural Science Edition），2013，38（2）：25-28.（in Chinese）

［13］陳祥恩，張忠輔，晏靜之，等.關(guān)于幾類特殊圖的Mycielski圖的鄰點(diǎn)可區(qū)別全色數(shù)（英文）［J］.蘭州大學(xué)學(xué)報(bào)（自然科學(xué)版），2005，41（2）：117-122.Chen Xiang'en，Zhang Zhongfu，Yan Jingzhi，et al.Adjacent-vertex-distinguishing total chromatic numbers on Mycielski's graph of several kinds of pareicular graphs［J］.Journal of Lanzhou University（Natural Science），2005，41（2）：117-122.（in Chinese）

［14］王繼順.圖M（Pn）和M（Cn）的點(diǎn)可區(qū)別邊色數(shù)［J］.數(shù)學(xué)雜志，2012，32（2）：363-368.Wang Jishun.Vertex-distinguishing edge chromatic number of M（Pn）and M（Cn）［J］.Journal of Math.，2012，32（2）：363-368.（in Chinese）

［15］Bollobas B.Modern graph theory［M］.New York：Springer-Verlag，1998.