三星的最優(yōu)的一般點(diǎn)可區(qū)別全染色

李 婷，陳祥恩，王治文

（1.西北師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，甘肅 蘭州 730070；2.寧夏大學(xué)數(shù)學(xué)計(jì)算機(jī)科學(xué)學(xué)院，寧廈 銀川 750021）

0 引言及準(zhǔn)備工作

點(diǎn)可區(qū)別一般邊染色是由Harary F等人于1985年在文獻(xiàn)[1]中提出的，在文獻(xiàn)[1-4]中均有研究.近些年來(lái)點(diǎn)可區(qū)別的未必正常的全染色也逐漸被研究.例如，點(diǎn)可區(qū)別IE-全染色在文獻(xiàn)[5]中被提出，而一般點(diǎn)可區(qū)別全染色在文獻(xiàn)[6]中被提出.

G 的 k-一般全染色 f是指從 V（G）∪E（G）到{1，2，…，k}的一個(gè)映射.

設(shè)f是G的一個(gè)一般全染色，若對(duì)圖G的任意兩個(gè)不同的頂點(diǎn)u，v，有C（u）≠C（v），則f稱為圖G的一般點(diǎn)可區(qū)別全染色（GVDTC）.

圖G的使用k種顏色的一般點(diǎn)可區(qū)別全染色稱為圖G的k-一般點(diǎn)可區(qū)別全染色（簡(jiǎn)記為k-GVDTC）.令圖G存在k-GVDTC}，則稱χgvt（G）為G的一般點(diǎn)可區(qū)別全色數(shù).

星Sn就是完全二部圖K1，n（n≥1）.稱Sm，n是雙星，如果Sm，n是樹，并且頂點(diǎn)集為邊集為其中 m，n 是正整數(shù)且均大于 1.稱 Sp，q，r是三星，如果 Sp，q，r是樹，并且頂點(diǎn)集為邊集為v0w0}，其中 p，q，r是正整數(shù).

文獻(xiàn)[6]中研究了路，圈，星（即K1，n），雙星，三星，輪，扇，完全圖的一般點(diǎn)可區(qū)別全染色，確定了它們的一般點(diǎn)可區(qū)別全色數(shù).但未給出三星的一般點(diǎn)可區(qū)別全色數(shù)這一結(jié)論的詳細(xì)證明，僅指出了思路.在本文中，我們將用一種不同于文獻(xiàn)[6]中指出的思路給出三星的最優(yōu)的一般點(diǎn)可區(qū)別全染色.

引理1[6]設(shè)Sn（n≥1）是一個(gè)星，則有

事實(shí)2設(shè)圖G有k-GVDTC，但圖G沒有（k-1）-GVDTC，則χgvt（G）＝k.

1 主要結(jié)果及其證明

定理 3 設(shè) Sp，q，r是一個(gè)三星，令 l＝p＋q＋r，則

證明：當(dāng)l＝3時(shí)，顯然χgvt（S1，1，1）≥3.因?yàn)?種顏色只能區(qū)別3個(gè)點(diǎn)，而圖1（a）給出了S1，1，1的3-GVDTC，因此χgvt（S1，1，1）＝3.

圖 1 S1，1，1，S1，1，2，S1，2，1 的3-GVDTC

當(dāng) l＝4 時(shí)，只需考慮 S1，1，2，S1，2，1即可.顯然對(duì)這 2 個(gè)圖，χgvt≥3.因?yàn)?2 種顏色只能區(qū)別3個(gè)點(diǎn)，而圖1中（b），（c）分別給出了這2個(gè)圖的3-GVDTC，因此χgvt（S1，1，2）＝χgvt（S1，2，1）＝3.

當(dāng) l＝5 時(shí)，只需考慮 S1，1，3，S1，3，1，S1，2，2，S2，1，2即可.顯然對(duì)這 4 個(gè)圖，χgvt≥4.因?yàn)?種顏色只能區(qū)分7個(gè)點(diǎn)，而圖2分別給出了這4個(gè)圖的4-GVDTC，故χgvt（S1，1，3）＝χgvt（S1，3，1）＝χgvt（S1，2，2）＝χgvt（S2，1，2）＝4.

當(dāng) l＝6 時(shí)，只需考慮 S1，1，4，S1，4，1，S1，2，3，S1，3，2，S2，1，3，S2，2，2即可.顯然對(duì)這 6 個(gè)圖，χgvt≥4.因?yàn)?種顏色只能區(qū)分7個(gè)點(diǎn)，而圖3分別給出了這6個(gè)圖的4-GVDTC，故χgvt（S1，1，4）＝χgvt（S1，4，1）＝χgvt（S1，2，3）＝χgvt（S1，3，2）＝χgvt（S2，1，3）＝χgvt（S2，2，2）＝4.

圖 2 S1，1，3，S1，3，1，S1，2，2，S2，1，2 的4-GVDTC

圖 3 S1，1，4，S1，4，1，S1，2，3，S1，3，2，S2，1，3，S2，2，2 的4-GVDTC

以下假設(shè)l≥7.

小正整數(shù).設(shè)u1，u2，u3是 Sp，q，r中度大于 1 的那 3 個(gè)頂點(diǎn)，Sp，q，r中與 u1相鄰的懸掛點(diǎn)為u1，1，…，u1，p；與 u2相鄰的懸掛點(diǎn)為 u2，1，…，u2，q；與 u3相鄰的懸掛點(diǎn)為u3，1，…，u3，r.

設(shè) G′是從 Sp，q，r中刪去 2 條邊 u1u2，u2u3后再將 3 個(gè)頂點(diǎn) u1，u2，u3等同所得的圖，則G′是階為l＋1的星，即G′?Sl，令w為G′的中心.由引理1知，Sl有k-GVDTC g，則G′也有k-GVDTC g，且不妨設(shè)G′的l條懸掛邊wu1，1到wu3，r的顏色是按從小到大的順序排列.下構(gòu)造 Sp，q，r的 k-GVDTC f.

讓 Sp，q，r的懸掛點(diǎn) u1，i沿襲在 g 下 G′中對(duì)應(yīng)的懸掛點(diǎn) u1，i的顏色，i＝1，2，…，p；讓 Sp，q，r的懸掛點(diǎn) u2，j沿襲在 g 下 G′中對(duì)應(yīng)的懸掛點(diǎn) u2，j的顏色，j＝1，2，…，q；讓 Sp，q，r的懸掛點(diǎn)u3，t沿襲在 g 下 G′中對(duì)應(yīng)的懸掛點(diǎn) u3，t的顏色，t＝1，2，…，r；讓 Sp，q，r的懸掛邊 u1u1，i沿襲在 g 下 G′中對(duì)應(yīng)的懸掛邊 wu1，i的顏色，i＝1，2，…，p；讓 Sp，q，r的懸掛邊 u2u2，j沿襲在g 下 G′中對(duì)應(yīng)的懸掛邊 wu2，j的顏色，j＝1，2，…，q；讓 Sp，q，r的懸掛邊 u3u3，t沿襲在 g 下G′中對(duì)應(yīng)的懸掛邊 wu3，t的顏色，t＝1，2，…，r.則在此基礎(chǔ)上以下只需考慮 u1，u1u2，u2，u2u3，u3的染色即可.

令A(yù)（ui）表示與ui關(guān)聯(lián)的懸掛邊的顏色構(gòu)成的集合（非多重集），i＝1，2，3.以下分4種情況討論.

在這種情況下，可按圖4 中（a），（b），（c）所給出的方式分 3 種情形對(duì) u1，u1u2，u2，u2u3，u3進(jìn)行染色.比如：在情形（a）中，點(diǎn) u1，u2，u3分別用 2，4，4 去染；邊 u1u2，u2u3分別用 3，2染.這時(shí)，C（u1）＝{1，2，3}，C（u2）＝{1，2，3，4}，C（u3）＝{1，2，4}，其它頂點(diǎn)即懸掛點(diǎn)的色集合為1-子集或2-子集，因此所得的染色是k-GVDTC.在其他情形下，都可類似得到最終染色是k-GVDTC，且不再贅述.

圖4 情況（1）的示意圖

情形（a）記為情形（1，1，1），情形（b）記為情形（1，1，2），情形（c）記為情形（1，2，3），除這 3種情形外，還有情形（1，2，2）等價(jià)于情形（b）.

注記：上圖均為示意圖，在上圖中只標(biāo)出了與u1，u2，u3關(guān)聯(lián)的懸掛邊顏色的種類，而與u1，u2，u3關(guān)聯(lián)的懸掛邊的條數(shù)不僅僅只有圖中出現(xiàn)的條數(shù).后面再出現(xiàn)時(shí)，不再作注解.

我們將圖 5中的情形（a）記為情形（1，1，12），情形（b）記為情形（1，1，23），其它類似.除上述 7種情形外，還有情形（12，2，2）與情形（a）等價(jià)；情形（12，3，3）與情形（b）等價(jià)；情形（12，2，3）與情形（c）等價(jià)；情形（12，3，4）與情形（d）等價(jià)；情形（1，23，3）與情形（f）等價(jià).因此，出現(xiàn)的這些情形將不再畫圖表示.

由懸掛邊染色規(guī)律可得，A（u2）≠A（u3），則 A（u3）A（u2）≠?且 A（u2）A（u3）≠?.設(shè)a，b∈A（u2），a＜b 且 a?A（u3），c，d∈A（u3），c＜d 且 d?A（u2）.

圖5 情況（2）的示意圖

我們用 d染u1；用{1，2，…，k}{c，d}中的兩種不同的顏色分別去染 u2u3與u3；用{1，2，…，k}{A（u1）∪g0gggggg}中某種顏色去染 u1u2；用{1，2，…，k}{a，b，d}中某種顏色去染 u2.

由懸掛邊染色規(guī)律可得，A（u1）≠A（u3），則 A（u3）A（u1）≠?且 A（u1）A（u3）≠?.設(shè)a，b∈A（u1），a＜b 且 a?A（u3），c，d∈A（u3），c＜d 且 d?A（u1）.

我們用 d染u2；用{1，2，…，k}{c，d}中的兩種不同的顏色分別去染 u2u3與 u3；當(dāng)A（u2）＝{f（u2u3）}時(shí)，用{1，2，…，k}{d，f（u2u3）}中的某種顏色去染u1u2；當(dāng)A（u2）≠{f（u2u3）}時(shí)，用 f（u2u3）去染 u1u2；用{1，2，…，k}{a，b，d}中某種顏色去染 u1.

由懸掛邊染色規(guī)律可得 A（u1），A（u2），A（u3）互不相同.設(shè) a，b∈A（u1），a＜b 這時(shí)只需用顏色k分別去染u1，u2，u1u2，u2u3；再用a染u3即可.顯然最終所得的染色是Sp，q，r的k-GVDTC.

綜上可得 Sp，q，r的 k-GVDTC f.

2 結(jié)語(yǔ)

本文定理2是在文獻(xiàn)[6]定理9的基礎(chǔ)上用一種更為優(yōu)化的方法探討并證明了三星具有一般點(diǎn)可區(qū)別全染色.另外，三星在3-階的路的基礎(chǔ)上加懸掛點(diǎn)得到的，那么這種方法是不是可以繼續(xù)延續(xù)下去，進(jìn)而得到在n-階的路上加懸掛點(diǎn)所得的圖的一般點(diǎn)可區(qū)別全色數(shù)？這就是今后需要繼續(xù)研究的課題.