三角金字塔網(wǎng)的點(diǎn)、邊、全色數(shù)*

喻雪榮

(浙江師范大學(xué)數(shù)理與信息工程學(xué)院，浙江金華 321004)

0 引 言

本文所考慮的圖均為有限簡(jiǎn)單的無向圖.對(duì)于圖G，分別用V(G)，E(G)和Δ(G)表示圖G的頂點(diǎn)集、邊集和最大度.圖染色的基本問題就是確定各種染色法的色數(shù)，目前已有許多研究結(jié)果［1-6］.

圖G的正常k-染色是指一個(gè)映射f:V(G)→{1，2，…，k}，滿足?uv∈E(G)，f(u)≠f(v);若G有一個(gè)正常k-染色，則稱圖G是k-可染的;色數(shù)χ(G)是指使得圖G是k-可染的最小整數(shù)k;圖G的正常k-邊染色是從邊集E(G)到顏色集合{1，2，…，k}的一個(gè)映射，使得相鄰的邊染不同的顏色;邊色數(shù)χ'(G)是指使得圖G是k-邊可染的最小整數(shù)k;圖G的k-全染色是用k種顏色對(duì)圖G的V(G)∪E(G)中的元素進(jìn)行染色，使得相鄰或者相關(guān)聯(lián)的兩元素染不同的顏色.全色數(shù)χT(G)是指使得圖G存在k-全染色的最小整數(shù) k.顯然，Δ(G)+1≤χT(G).

三角金字塔網(wǎng)TPL是由Razivi和Sarbazi-Azad在三角格網(wǎng)Tn的基礎(chǔ)上提出來的一個(gè)分層網(wǎng)絡(luò).文獻(xiàn)［7］給出了TPL的色數(shù)的上界，即χ(TPL)≤6.本文確定了TPL的點(diǎn)色數(shù)χ(TPL)、邊色數(shù)χ'(TPL)和全色數(shù)χT(TPL).

1 三角金字塔網(wǎng)

首先介紹一下三角格網(wǎng)Tn的定義.

定義1 用Tn表示層數(shù)為n的三角格網(wǎng)，其頂點(diǎn)集為 V(Tn)={(x，y)|0≤x+y≤n}，Tn中的2 個(gè)點(diǎn)(x1，y1)和(x2，y2)相鄰當(dāng)且僅當(dāng)|x1-x2|+|y1-y2|=1，或 x2=x1+1 且y2=y1-1，或 x2=x1-1 且 y2=y1+1.

圖1為4層三角格網(wǎng)T4.

定義2 用TPL表示L層三角金字塔網(wǎng)，其頂點(diǎn)集為 V(TPL)={(k，x，y)|0≤k≤L，0≤x+y≤k}.點(diǎn)(k，x，y)表示第 k層坐標(biāo)為(x，y)的點(diǎn).k 層的點(diǎn)集構(gòu)成一個(gè)三角格網(wǎng) Tk，k 層的點(diǎn)(k，x，y)與k+1層的點(diǎn)(k+1，x，y)，(k+1，x+1，y)和(k+1，x，y+1)相鄰.

圖1 4層三角格網(wǎng)T4

圖2為4層三角金字塔網(wǎng)TP4.

圖G中頂點(diǎn)v所關(guān)聯(lián)的邊的數(shù)目稱為頂點(diǎn)v的度，記為dG(v)或d(v).

由TPL的定義知，TPL中的點(diǎn)度有3，6，9 或 12，當(dāng)且僅當(dāng) L≥4 時(shí)，Δ(TPL)=12.若點(diǎn)u的頂點(diǎn)度為12，則它的鄰點(diǎn)集為 N(u)={(k-1，x-1，y)，(k-1，x，y)，(k-1，x，y-1)，(k，x-1，y)，(k，x-1，y+1)，(k，x，y-1)，(k，x，y+1)，(k，x+1，y-1)，(k，x+1，y)，(k+1，x，y)，(k+1，x，y+1)，(k+1，x+1，y)}.TPL的點(diǎn)數(shù)和邊數(shù)分別為(L+2).

圖2 4層三角金字塔網(wǎng)TP4

2 主要結(jié)果

定理1 當(dāng)L≥1時(shí)，TPL的色數(shù)是χ(TPL)=4.

證明 當(dāng)L≥1時(shí)，因?yàn)門PL含有完全子圖K4，所以χ(TPL)≥χ(K4)=4.

下證χ(TPL)≤4.根據(jù)點(diǎn)的每個(gè)分量的奇偶性將TPL的頂點(diǎn)集合V(TPL)分成4個(gè)集合，V1={(偶，偶，偶)，(奇，奇，奇)}，V2={(偶，偶，奇)，(奇，奇，偶)}，V3={(偶，奇，偶)，(奇，偶，奇)}，V4={(奇，偶，偶)，(偶，奇，奇)}.由TPL的定義知，圖TPL中的任意一個(gè)點(diǎn)u與它的鄰點(diǎn)至少有1個(gè)分量的奇偶性相同，故 Vi(i=1，2，3，4)是獨(dú)立集.將 Vi(i=1，2，3，4)中的點(diǎn)染顏色 i，則任意2 個(gè)相鄰的點(diǎn)染不同的顏色，所以χ(TPL)≤4.定理1證畢.

定理2 當(dāng)L≥4時(shí)，TPL的邊色數(shù)是χ'(TPL)=12.

證明 當(dāng)L≥4時(shí)，Δ(TPL)=12，故有 χ'(TPL)≥12.

下證χ'(TPL)≤12.只須給出TPL的一個(gè)正常12-邊染色即可.可以將TPL看成是由6個(gè)不同方向的多條路組成的圖.設(shè)點(diǎn)v的點(diǎn)度為12，與v相關(guān)聯(lián)的邊集分成6個(gè)不同方向:

在li(i∈{1，2，…，6})方向上的邊交錯(cuò)染顏色2i-1和2i.對(duì)TPL中任意點(diǎn)u，與它相關(guān)聯(lián)的所有邊都在上述6個(gè)方向上，并且不同方向的邊染不同顏色，在同一個(gè)方向上的2條邊也染不同的顏色.所以，χ'(TPL)≤12.定理2證畢.

定理3 當(dāng)L≥4時(shí)，TPL的全色數(shù)是χT(TPL)=13.

證明 當(dāng)L≥4時(shí)，Δ(TPL)=12，故有 χT(TPL)≥Δ(TPL)+1=13.

下證χT(TPL)≤13.只須給出TPL的一個(gè)正常13-全染色即可.

首先根據(jù)定理1的染色規(guī)則，給TPL的頂點(diǎn)染4種顏色{1，2，3，4}，并記4種顏色的點(diǎn)集分別為V1，V2，V3，V4.根據(jù) TPL的定義和定理 2，在 k 層上的邊共有 3 個(gè)方向 l3，l4，l5，再用 6 種顏色{5，6，7，8，9，10}，根據(jù)定理2的染色規(guī)則，給TPL在k(1≤k≤L)層上的邊進(jìn)行染色.

用E1表示k(k為奇數(shù))層與k+1層之間的邊集，用E2表示k(k為偶數(shù))層與k+1層之間的邊集，用 E1［Vi，Vj］表示 k(k為奇數(shù))層染顏色i的點(diǎn)與 k+1層染顏色 j的點(diǎn)之間的邊集，用 E2［Vi，Vj］表示k(k為偶數(shù))層染顏色i的點(diǎn)與k+1層染顏色j的點(diǎn)之間的邊集.

用4 種顏色{1，2，3，4}來染 E1中的邊.若 e∈E1［V2，V3］∪E1［V3，V4］∪E1［V4，V2］，則將邊 e染顏色 1;若 e∈E1［V1，V4］∪E1［V3，V1］∪E1［V4，V3］，則染顏色 2;若 e∈E1［V1，V2］∪E1［V2，V4］∪E1［V4，V1］，則染顏色 3;若 e∈E1［V1，V3］∪E1［V2，V1］∪E1［V3，V2］，則染顏色 4.

用 3 種顏色{11，12，13}來染 E2中的邊.若 e∈E2［V1，V2］∪E2［V2，V4］∪E2［V3，V1］∪E2［V4，V3］，則將邊 e染顏色 11;若 e∈E2［V1，V3］∪E2［V2，V1］∪E2［V3，V4］∪E2［V4，V2］，則染顏色 12;若 e∈E2［V1，V4］∪E2［V2，V3］∪E2［V3，V2］∪E2［V4，V1］，則染顏色 13.

根據(jù)定理1，任意相鄰兩點(diǎn)都染不同顏色，由給出的邊的染色規(guī)則，易驗(yàn)證任意相鄰兩邊或相關(guān)聯(lián)的點(diǎn)和邊都染不同的顏色.定理3證畢.

［1］Jakovac M，Klav?ar S.Vertex-，edge-，and total-colorings ofgraphs［J］.Discrete Mathematics，2009，309(6):1548-1556.

［2］Chen Meirun，Guo Xiaofeng.Adjacent vertex-distinguishing edge and total chromatic numbers of hypercubes［J］.Information Processing Letters，2009，109(12):599-602.

［3］Liu Bin，Hou Jianfeng，Wu Jianliang，et al.Total colorings and list total colorings of planar graphs without intersecting 4-cycles［J］.Discrete Mathematics，2009，309(20):6035-6043.

［4］薛玲，吳建良.較少短圈的平面圖的全色數(shù)［J］.山東大學(xué)學(xué)報(bào):理學(xué)版，2012，47(9):84-87.

［5］王侃.最大度為6的平面圖是13-線性可染的［J］.浙江師范大學(xué)學(xué)報(bào):自然科學(xué)版，2012，35(2):121-124.

［6］傅彩霞.若干倍圖的均勻染色［J］.浙江師范大學(xué)學(xué)報(bào):自然科學(xué)版，2012，35(2):133-137.

［7］Razavi S，Sarbazi-Azad H.The triangular pyramid:routing and topological properties［J］.Information Sciences，2010，180(11):2328-2339.