趙亞迪, 陳祥恩

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

1 引言與預備知識

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

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

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

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

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

定義1設1≤i1

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

圖1 圖C15的全染色

2 主要結(jié)果

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

證畢.

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

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