路、扇及星的Mycielski圖的鄰點可區(qū)別I-全染色

劉秀麗

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

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

定義1［9，12］對于階數(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的鄰點可區(qū)別I-全染色（簡記作k-IAVDTC），記χiat（G）=min｛k|G有k-鄰點可區(qū)別I-全染色｝為G的鄰點可區(qū)別I-全色數(shù).

定義2［13-14］設圖G是簡單圖，構造圖M（G），使

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

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

本文所討論的圖均為簡單、有限圖.文中未加說明的記號和術語參見文獻［1，15］.

1 主要結果及證明

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

證明 1）n=3.

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

此時

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

2）n=4.

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

此時

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

3）n≥5.

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

此時

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

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

證明 1）n=3.

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

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

2）n≥4.

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

此時

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

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

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

此時

綜上，f是M（Sn）的一個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］張忠輔，陳祥恩，李敬文，等.關于圖的鄰點可區(qū)別全染色［J］.中國科學（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］孫曉玲，杜建偉.一類外平面圖的鄰點可區(qū)別全染色［J］.中北大學學報（自然科學版），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的鄰點可區(qū)別全色數(shù)［J］.數(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］楊超，姚兵，王宏宇.復合交叉圈的鄰點可區(qū)別全色數(shù)［J］.華南師范大學學報（自然科學版），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］王治文，楊隨義，文飛.關于若干倍圖的關聯(lián)鄰點可區(qū)別全染色［J］.內蒙古師范大學學報（自然科學漢文版），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-正則圖的關聯(lián)鄰點可區(qū)別全染色［J］.山西大學學報（自然科學版），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］盧建立，任鳳霞，馬美琳.項鏈的若干染色問題［J］.科技導報，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的鄰點可區(qū)別的I-全染色［J］.純粹數(shù)學與應用數(shù)學，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的鄰點可區(qū)別I-全染色［J］.數(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的鄰點可區(qū)別的I-全染色［J］.西南師范大學學報（自然科學版），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］陳祥恩，張忠輔，晏靜之，等.關于幾類特殊圖的Mycielski圖的鄰點可區(qū)別全色數(shù)（英文）［J］.蘭州大學學報（自然科學版），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）的點可區(qū)別邊色數(shù)［J］.數(shù)學雜志，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.