李 婷，陳祥恩，王治文

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

0 引言及準備工作

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

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

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

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

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

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

引理1[6]設Sn（n≥1）是一個星，則有

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

1 主要結果及其證明

定理 3 設 Sp，q，r是一個三星，令 l＝p＋q＋r，則

證明：當l＝3時，顯然χgvt（S1，1，1）≥3.因為2種顏色只能區(qū)別3個點，而圖1（a）給出了S1，1，1的3-GVDTC，因此χgvt（S1，1，1）＝3.

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

當 l＝4 時，只需考慮 S1，1，2，S1，2，1即可.顯然對這 2 個圖，χgvt≥3.因為 2 種顏色只能區(qū)別3個點，而圖1中（b），（c）分別給出了這2個圖的3-GVDTC，因此χgvt（S1，1，2）＝χgvt（S1，2，1）＝3.

當 l＝5 時，只需考慮 S1，1，3，S1，3，1，S1，2，2，S2，1，2即可.顯然對這 4 個圖，χgvt≥4.因為3種顏色只能區(qū)分7個點，而圖2分別給出了這4個圖的4-GVDTC，故χgvt（S1，1，3）＝χgvt（S1，3，1）＝χgvt（S1，2，2）＝χgvt（S2，1，2）＝4.

當 l＝6 時，只需考慮 S1，1，4，S1，4，1，S1，2，3，S1，3，2，S2，1，3，S2，2，2即可.顯然對這 6 個圖，χgvt≥4.因為3種顏色只能區(qū)分7個點，而圖3分別給出了這6個圖的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

以下假設l≥7.

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

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

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

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

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

圖4 情況（1）的示意圖

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

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

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

由懸掛邊染色規(guī)律可得，A（u2）≠A（u3），則 A（u3）A（u2）≠?且 A（u2）A（u3）≠?.設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）∪syggg00}中某種顏色去染 u1u2；用{1，2，…，k}{a，b，d}中某種顏色去染 u2.

由懸掛邊染色規(guī)律可得，A（u1）≠A（u3），則 A（u3）A（u1）≠?且 A（u1）A（u3）≠?.設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；當A（u2）＝{f（u2u3）}時，用{1，2，…，k}{d，f（u2u3）}中的某種顏色去染u1u2；當A（u2）≠{f（u2u3）}時，用 f（u2u3）去染 u1u2；用{1，2，…，k}{a，b，d}中某種顏色去染 u1.

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

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

2 結語

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