平方圖的2-距離和可區(qū)別邊染色

王芹,楊超,姚兵

(1.上海工程技術(shù)大學(xué) 數(shù)理與統(tǒng)計(jì)學(xué)院;智能計(jì)算與應(yīng)用統(tǒng)計(jì)研究中心,上海 201620;2.西北師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,蘭州 730070)

1 預(yù)備知識

染色問題是圖論中的經(jīng)典問題之一,具有較強(qiáng)的應(yīng)用背景,它解決了如存儲問題、課程表問題、電路設(shè)計(jì)等眾多實(shí)際問題[1].2002年,ZHANG等[1]首次提出了圖的鄰點(diǎn)可區(qū)別正常邊染色,即在正常邊染色的基礎(chǔ)上區(qū)分相鄰點(diǎn)的色集合,相關(guān)研究成果詳見文獻(xiàn)[2-8].對于兩個不同的集合,它們的元素之和可能會相同,但若兩個集合元素之和不同,則這兩個集合一定不同.2013年,FLANDRIN等[9]提出了圖的鄰和可區(qū)別正常邊染色,需要考慮相鄰頂點(diǎn)邊色集合的元素之和,即圖G的一個正常邊染色滿足任意相鄰兩點(diǎn)的色集合的元素之和不同.2021年,強(qiáng)會英等[10]在鄰和可區(qū)別邊染色的基礎(chǔ)上考慮將相鄰點(diǎn)擴(kuò)展為距離不超過2的點(diǎn),提出了圖的2-距離和可區(qū)別邊染色的概念,并研究了無K4-子式圖的2-距離和可區(qū)別邊染色.本文探討5類平方圖的2-距離和可區(qū)別邊色數(shù)問題.

定義2設(shè)u和ν分別表示連通圖G和H中的最小度點(diǎn),稱圖G∧H表示將G中的點(diǎn)u與H中的點(diǎn)ν粘連一起后得到的圖.

定義3[11]圖G的平方圖G2是以V(G)作為它的點(diǎn)集,任意兩個點(diǎn)u,ν在G2中相鄰當(dāng)且僅當(dāng)1≤distG(u,ν)≤2.

本文論及的圖均為有限、無向、連通的簡單圖.設(shè)N(u)表示u的鄰點(diǎn)集,Δ(G)(或Δ)表示圖的最大度;設(shè)u,ν為圖G中任意兩點(diǎn),稱滿足DG(u,ν)≤2的點(diǎn)為2-距離點(diǎn).文中未定義的術(shù)語和符號均采用于文獻(xiàn)[13].

2 主要結(jié)論

情形1n≡0(mod 5)

情形2n≠0(mod 5)

情形1n≡0(mod 5)

情形2n?0(mod 5)

綜上所述,結(jié)論成立.