多重圖的邊著色研究

鄭學謙， 喬曉云

（山西大學商務學院，山西 太原 030031）

0 引 言

圖論是數學的一個分支，是近年來發展迅速而又應用廣泛的一門新興學科。圖的著色問題［1］是圖論中十分活躍的研究課題，有著深刻而豐富的理論結果和廣泛的實際應用，諸如時間表問題、排課表問題、存儲問題等，其理論和方法在離散數學中占有重要地位。Ving［2－3］等很早就研究了多重圖的色數問題；唐明元［4］研究了滿足2色P4條件完全圖的邊著色；王俊梅［5］研究了四類圈樹的連續邊著色；張鑫［6］等研究了環形圖的邊著色。在此基礎上，文中定義了多重圖的R（k，n：p）－邊著色，并利用正交拉丁方和矩陣的乘法證明了當m≡0（mod2）時，圖是R（2，m：4）－邊著色圖。

1 基本概念

定義1［7］M稱為r－多重完全圖，如果M的任意兩個不同的頂點都有r條邊。n階的r－多重完全圖記為

定義2［7］多重圖m邊著色指的是每一條邊著給定的m種顏色中的一種，任意兩個頂點之間的邊著不同顏色。

定義4［8］設n為正整數，S＝｛0，1，2，…，n－1｝，使得S中的n個元素中的每一個均在每一行出現一次（從而恰好一次）且在每一列出現一次，即每一行和每一列都是S的元素的一個排列，這樣組成的n×n矩陣A稱為n階拉丁方。

2 主要結果

證明 第1步：利用模n的加法運算得到偶數階對稱拉丁方A2，A4，A6，…，A2n，…

第2步：利用算法構造對角線元素全是0偶階對稱拉丁方。

算法如下：

1）把每一行（除去第一行和最后一行）中要放到最后一列的數找出。這個數的位置根據如下規律確定：

2）把拉丁方A2n中對角線的元素aii和由1）找到的數提出，這行的其它數將向左移1位。

3）將矩陣對角線上的元素放在該行對角線的位置上，將剩下的另一個數放在最后一列。

4）最后一行元素由對稱所得。

第3步：將矩陣A2與A2n作運算得出圖的邊標號，其中（i，j）表示vivj二重邊的標號。

，…

…

［1］ Bondy J A，Murty U S R.Graph theory with applications［M］.New York：The Macmillan Press Ltd.，1976.

［2］ Ving V.The chromatic class of multigraph［J］.Cybernetics，1965（1）：32－41.

［3］ Steffen E.A refinement of vings theorem［J］.Cybernetics，2000（1）：289－291.

［4］ 唐明元.滿足5色K4條件完全圖的邊著色［J］.上海師范大學學報：自然科學版，2003（3）：21－25.

［5］ 王俊梅.四類圈樹的連續邊著色［J］.太原師范學院學報：自然科學版，2012（4）：4－6.

［6］ Zhang Xin，Liu Guizhen.On edge colorings of 1－toroidal graphs［J］.數學學報：英文版，2013（7）：1421－1428.

［7］ 邵澤輝.Ramsey理論中圖的構造與計算［D］.武漢：華中科技大學，2008.

［8］ 馮舜璽.組合數學［M］.北京：機械工業出版社，2005.