圖mC15的點(diǎn)可區(qū)別Ⅰ-全染色和Ⅵ-全染色

趙亞迪, 陳祥恩

(西北師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院, 蘭州 730070)

1 引言與預(yù)備知識(shí)

目前, 關(guān)于圖的點(diǎn)可區(qū)別的正常邊染色與點(diǎn)可區(qū)別的一般邊染色研究已有很多結(jié)果[1-6]. 圖G的一個(gè)k-全染色是指用k種顏色{1,2,…,k}對(duì)圖G的全體頂點(diǎn)及邊的一個(gè)分配, 對(duì)圖G的每個(gè)頂點(diǎn)y,Cf(y)指在f下點(diǎn)y的顏色及與y關(guān)聯(lián)的全體邊的顏色構(gòu)成的集合(非多重集), 稱為y的色集合. 設(shè)f是圖G的一個(gè)正常全染色, 如果對(duì)?u,v∈V,u≠v, 有C(u)≠C(v), 則稱f是圖G的點(diǎn)可區(qū)別全染色(VDTC)[7-8].

本文所研究的圖均為有限的無向簡(jiǎn)單圖, 考慮點(diǎn)可區(qū)別的一類未必正常的全染色. 設(shè)f為圖G的k-全染色, 若任意兩個(gè)相鄰頂點(diǎn)在f下的色不相同, 且任意兩條相鄰邊在f下的色也不相同, 則該染色f稱為圖G的Ⅰ-全染色. 如果在f下圖G的任意相鄰兩條邊均染不同顏色, 則稱f為Ⅵ-全染色. 易知Ⅰ-全染色必為Ⅵ-全染色[9-10]. 設(shè)f為圖G的Ⅰ-全染色(Ⅵ-全染色), 若圖G任意兩個(gè)頂點(diǎn)的色集合均不相同, 則稱f是點(diǎn)可區(qū)別的. 分配k種顏色的點(diǎn)可區(qū)別的Ⅰ-全染色簡(jiǎn)記為k-VDITC(k-點(diǎn)可區(qū)別的Ⅵ-全染色簡(jiǎn)記為k-VDVITC).

顯然圖的VDITC一定是圖的VDVITC, 因此本文只需討論圖的最優(yōu)VDITC, 從而可得出圖的最優(yōu)VDVITC. Chen等[10]提出了圖的VDITC和圖的VDVITC, 從而確定了完全圖、 完全二部圖、 輪、 扇、 正規(guī)雙星、 路、 圈等圖類的點(diǎn)可區(qū)別的Ⅰ-全色數(shù)以及點(diǎn)可區(qū)別的Ⅵ-全色數(shù), 并提出了以下猜想.

苗婷婷等[11-12]研究了兩條路的聯(lián)圖、 圈與路的聯(lián)圖、 圈與圈、 圈與輪、 圈與扇的聯(lián)圖的VDITC和VDVITC； 楊晗等[13]研究了m個(gè)階為4的圈的不交并的點(diǎn)可區(qū)別的Ⅰ-全染色和Ⅵ-全染色. 本文通過構(gòu)造m個(gè)長(zhǎng)為15的圈的不交并mC15的最優(yōu)VDITC, 確定mC15的點(diǎn)可區(qū)別Ⅰ-全色數(shù)以及當(dāng)m≥1時(shí)mC15的點(diǎn)可區(qū)別Ⅵ-全色數(shù). 結(jié)果表明: 對(duì)于圖mC15, VDITC猜想和VDVITC猜想均成立.

構(gòu)造如下(n-1)×(n-1)階矩陣An(n≥5), 使矩陣An中元素是集合{1,2,…,n}的含n的2-子集、 3-子集(即構(gòu)造某個(gè)VDITC下點(diǎn)的色集合, 非多重集)或空集, 其中第i行含有(i-1)個(gè)?：

定義1設(shè)1≤i1

定義2若矩陣An的15個(gè)元素(非空)恰為C15的某個(gè)VDITC下C15全體頂點(diǎn)的色集合, 則稱由這15個(gè)元素構(gòu)成的組為一個(gè)好組.

圖1 圖C15的全染色

2 主要結(jié)果

下面考慮剩余元素為{k,i,k-1}(i=1,2,…,n-1)的染色.

證畢.

由命題1和定理1可得如下結(jié)論：

本文結(jié)論表明VDITC和VDVITC猜想對(duì)圖mC15也成立.