圖mC15的點可區別Ⅰ-全染色和Ⅵ-全染色

趙亞迪, 陳祥恩

(西北師范大學 數學與統計學院, 蘭州 730070)

1 引言與預備知識

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

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

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

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

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

定義1設1≤i1

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

圖1 圖C15的全染色

2 主要結果

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

證畢.

由命題1和定理1可得如下結論：

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