K5;5; p 的點(diǎn)可區(qū)別的 IE-全染色(p ?2 028)

閆瑞敏 陳祥恩

摘要： 圖 G 的 IE-全染色 f 是指對(duì)?u; v ∈ V（G） ， 使得 f （u）? f （v）的一個(gè)一般全染色 ， 其中 u; v 相鄰 ， V（G）是圖 G 的頂點(diǎn)集.設(shè) f 是圖 G 的 IE-全染色 ， 圖 G 的一個(gè)頂點(diǎn) x 在 f 下的色集合C（x）是指由x 及 x 的關(guān)聯(lián)邊的顏色所構(gòu)成的集合（非多重集）.若圖 G 的任意兩個(gè)不同頂點(diǎn)的色集合不同 ， 則 f 稱(chēng)為圖 G 的點(diǎn)可區(qū)別的 IE-全染色（簡(jiǎn)記為VDIETC）.利用色集合事先分配法、構(gòu)造染色法及反證法探討了完全三部圖 K5;5;p （p ?2 028）的點(diǎn)可區(qū)別的 IE-全染色問(wèn)題 ， 確定了 K5;5;p?? （p ?2 028）的點(diǎn)可區(qū)別的 IE-全色數(shù).

關(guān)鍵詞：完全三部圖;? IE-全染色;? 點(diǎn)可區(qū)別的 IE-全染色;? 點(diǎn)可區(qū)別的 IE-全色數(shù)

中圖分類(lèi)號(hào)： O157.5??? 文獻(xiàn)標(biāo)志碼： A??? DOI： 10.3969/j.issn.1000-5641.2022.02.003

Vertex-distinguishing IE-total coloring of K5; 5; p?? （p ?2 028）

YAN Ruimin，? CHEN Xiangen

（College of Mathematics and Statistics， Northwest Normal University， Lanzhou? 730070， China）

Abstract： Let G? be a simple graph. A total coloring f? of G? is called an IE-total coloring if f （u）? f （v） for any two adjacent vertices u? and v ， where V（G） denotes the set of vertices of G . For an IE-total coloring f? of G ， the set of colors C（x） （non-multiple sets） of vertex x? under f? of G? is the set of colors of vertex x? and of the edges incident with x . If any two distinct vertices of G? have distinct color sets， then f? is called a vertex-distinguishing IE-total coloring of G . We explore the vertex distinguishing IE-total coloringof complete tripartite graphs K5;5;p （p ?2 028） through the use of multiple methods， including distributing the color sets in advance， constructing the colorings， and contradiction. The vertex-distinguishing IE-total chromatic number of K5;5;p （p ?2 028） is determined.

Keywords： complete tripartite graph;?? IE-total coloring;?? vertex-distinguishing IE-total coloring;?? vertex- distinguishing IE-total chromatic number

0? 引言

點(diǎn)可區(qū)別一般邊染色在文獻(xiàn)[1-6]中均有研究 .近年來(lái) ， 點(diǎn)可區(qū)別的未必正常的全染色也被研究. 在文獻(xiàn)[7]中提出了點(diǎn)可區(qū)別的 IE-全染色. 文獻(xiàn)[8]對(duì)點(diǎn)可區(qū)別一般全染色進(jìn)行了討論 ， 文獻(xiàn) [9-11]對(duì)圖的優(yōu)美性、線性代數(shù)理論以及圖和星的合成的點(diǎn)可區(qū)別正常邊染色給出了相關(guān)結(jié)果.文獻(xiàn)[12]研究了完全三部圖 K2;n;p?? （2? n ?5）的點(diǎn)可區(qū)別的 IE-全染色和一般全染色 ， 并確定了它們的點(diǎn)可區(qū)別的 IE-全色數(shù)和一般全色數(shù).

圖G 的 IE-全染色f 是指對(duì)圖G 的任意2個(gè)相鄰頂點(diǎn)u; v ， 使得f （u）? f （v）的一個(gè)一般全染色;圖G 的 k-IE-全染色是指使用了k 種顏色的圖G 的 IE-全染色;圖G 的 k-點(diǎn)可區(qū)別的 IE-全染色是指使用了 k 種顏色的點(diǎn)可區(qū)別的 IE-全染色（簡(jiǎn)記為k-VDIETC）.點(diǎn)可區(qū)別是指圖G 中任意2個(gè)不同的頂點(diǎn)的色集合不同. 圖G 的 IE-全色數(shù)是指對(duì)圖G 進(jìn)行 IE-全染色所需要的最少顏色數(shù);圖G的點(diǎn)可區(qū)別的 IE-全色數(shù)是指對(duì)圖G進(jìn)行點(diǎn)可區(qū)別的 IE-全染色所需要的最少顏色數(shù) ， 記為vt（ie）（G）.

本文研究 K5;5;p 的點(diǎn)可區(qū)別的 IE-全染色 ， 并給出了它們的點(diǎn)可區(qū)別 IE-全色數(shù). 文中述及的完全三部圖 Km;n;p 的頂點(diǎn)集合為 V = X ∪ Y ∪ Z ， 其中 X ={x1; x2; ·· ·; xm}; Y ={y1; y2; ·· ·; yn}; Z ={z1; z2; ·· ·; zp} ， 邊集合為{xiyj |i =1;2;· ·· ; m; j =1;2;· ·· ; n}∪ {yjzt|j =1;2;· ·· ; n; t =1;2;· ·· ; p}∪{xizt |i =1;2;· ·· ; m; t =1;2;· ·· ; p}.FCD86179-7F39-4C2E-AD6D-ACE81DE4BD3A

本文約定：當(dāng)考慮圖 G 的 l-VDIETC 時(shí) ， 用 C（x）表示點(diǎn) x 的色集合在全體顏色構(gòu)成的集合 {1;2;· ·· ; l}中的補(bǔ)集 ， 即 C（x）= {1;2;· ·· ; l}＼C（x）. {1;2;· ·· ; l}的含有i 個(gè)元素的子集叫i -子集.

1? 準(zhǔn)備工作

引理1當(dāng) k ?14且p >? （k i 1）? 10時(shí) ， K5;5;p 不存在（k ?1）-VDIETC.

證明用反證法. 假設(shè) K5;5;p 存在（k?1）-VDIETC， 設(shè)為 g.

斷言1? ?a ∈{1;2;· ·· ; k ?1} ， {a}不是 X ∪ Y 中任一點(diǎn)的色集合.

否則 ， 不妨設(shè)a =1 且C（x1）= {1} ， 則 Z 中每個(gè)點(diǎn)的色集合必含1， 故p ? ∑（k i2） ， 與p >∑ （k i 1）?10矛盾.

斷言2? 任意2 -子集均不是 X ∪ Y 中任一點(diǎn)的色集合.

否則 ， 不妨設(shè)C（x1）= {1;2}且g（x1）= 1. 此時(shí) Z 中每個(gè)點(diǎn)的色集合必含1 或2.在{1;2;· ·· ; k ?1}中， 含1 不含2 且最多含有11個(gè)元素的子集的個(gè)數(shù)為 （k i3）;含 2不含1 且最多含有11個(gè)元素的子集的個(gè)數(shù)為∑ （k i3）;同時(shí)含1 和2 且最多含有11個(gè)元素的子集的個(gè)數(shù)為∑ （k i3） ， 故p ? ∑（k i3）+∑（k i3）+∑ （k i3） ， 這與p >∑ （k i 1）? 10矛盾.

斷言3? 任意3-子集均不是 X ∪ Y 中任一點(diǎn)的色集合.

否則 ， 不妨設(shè) C（x1）= {1;2;3}且 g（x1）= 1. 此時(shí) Z 中每個(gè)點(diǎn)的色集合必含1， 2或 3.在 {1;2;· ·· ;k ?1}中 ， 含1 不含2 和3 且最多含有11個(gè)元素的子集的個(gè)數(shù)為 （k i4）;含 2不含1 和3 且最多含有11個(gè)元素的子集的個(gè)數(shù)為∑ （k i4）;含 3不含1 和2 且最多含有11個(gè)元素的子集的個(gè)數(shù)為∑ （k i4）;含1 和2但不含3 且最多含有11個(gè)元素的子集的個(gè)數(shù)為 （k i4）;含 1和 3但不含2 且最多含有11個(gè)元素的子集的個(gè)數(shù)為∑ （k i4）;含 2和 3但不含1 且最多含有11個(gè)元素的子集的個(gè)數(shù)為∑ （k i4）;同時(shí)含1，2，3， 且最多含有11個(gè)元素的子集的個(gè)數(shù)為 ， 故，矛盾.

（1）當(dāng) {g（xi）|i =1;2;3;4;5}∪ {g（yj）|j =1;2;3;4;5}里互不相同的顏色至少有 3種時(shí) ， 不妨設(shè) {1;2;3}? {g（xi）|i =1;2;3;4;5}∪ {g（yj）|j =1;2;3;4;5} ， 那么{1}; {2}; {3}; {1;2}; {1;3};{2;3};{1;2;3}均不能作為 Z 中任一點(diǎn)的色集合 ， 由斷言1—3可知 ， {1};{2};{3};{1;2};{1;3};{2;3};{1;2;3}也均不是 X ∪ Y 中任一點(diǎn)的色集合 ，? C（xi）? {1;2;3} ，? C（yj）? {1;2;3} ， i; j =1;2;3;4;5 ， 且 C（xi）和 C（yj）（i; j =1;2;3;4;5）中最多有6 個(gè)集合屬于{{1}; {2}; {3}; {1;2}; {1;3}; {2;3}}. 因此 ， 這10個(gè)集合中至少還有4 個(gè)集合均不屬于{{1};{2};{3};{1;2};{1;3};{2;3};{1;2;3}} ， 不妨設(shè)為 C（x1） ， C（y1） ， C（y2） ，C（y3） ， 其中至少有1 個(gè)是? ， 不妨設(shè) C（x1）= ? ， C（yj）? ?; j =1;2;3 .

當(dāng) |C（y1）|? 11 ， |C（y2）|? 11 ， |C（y3）|? 11時(shí) ， {1};{2};{3};{1;2};{1;3};{2;3};{1;2;3} ，? C（y1） ，C（y2） ， C（y3）均不是 Z 中任一點(diǎn)的色集合 ， 故p ? ∑（k i 1）? 10 ， 與p >∑ （k i 1）? 10矛盾.

當(dāng) |C（y1）|? 11 ， |C（y2）|? 11 ， |C（y3）|? 12時(shí) ， {1};{2};{3};{1;2};{1;3};{2;3};{1;2;3} ，? C（y1） ，C（y2）及? C（y3）的 1-子集 ， 2 -子集 ， · ·· ;? 11-子集均不是 Z 中任一點(diǎn)的色集合 ， 故p ? ∑（k i 1）? 9? ∑（1i2）= ∑（k i 1）? 4103 ， 與p >∑ （k i 1）? 10矛盾.

當(dāng)|C（y1）|? 11 ， |C（y2）|? 12 ， |C（y3）|? 12時(shí) ， {1};{2};{3};{1;2};{1;3};{2;3};{1;2;3} ，? C（y1）及 C（yj） ，? j =2;3 ， 的 1-子集 ， 2 -子集 ， · ·· ;? 11-子集均不是 Z 中任一點(diǎn)的色集合 ， 故p ? ∑（k i 1）? 8? 2∑ （1i2）= ∑（k i 1）? 8196 ， 與p >∑ （k i 1）? 10矛盾.

當(dāng)|C（y1）|? 12 ， |C（y2）|? 12 ， |C（y3）|? 12時(shí) ， C（yj） （j =1;2;3 ）的 1-子集 ， 2-子集 ， ·· ·; 11-子集均不是 Z 中任一點(diǎn)的色集合 ， 故p ? ∑（k i 1）? 3∑ （1i2）= ∑（k i 1）? 12282 ， 與p >∑ （k i 1）? 10矛盾.FCD86179-7F39-4C2E-AD6D-ACE81DE4BD3A

（2）當(dāng) {g（xi）|i =1;2;3;4;5}∪ {g（yj）|j =1;2;3;4;5}里互不相同的顏色僅有2 種時(shí) ， 設(shè) g（xi）= 1; g（yj）= 2（i; j =1;2;3;4;5）.

斷言4? 在（2）下， {1};{2};{1;2}均不能作為 Z 中任一點(diǎn)的色集合.

斷言5? 在（2）下， {3};{4};{5};· ·· ;{k ?1}中至少有2 個(gè)集合不是 Z 中任一點(diǎn)的色集合.

否則 ， 至多有1 個(gè)集合不是 Z 中任一點(diǎn)的色集合， 不妨設(shè){4};{5};· ·· ;{k ?1}均是 Z 中任一點(diǎn)的色集合 ， 則 C（xi）∩ C（yj）? {4;5;· ·· ; k ?1}; i; j =1;2;3;4;5 ， 此時(shí) C（xi）; C（yj）; i; j =1;2;3;4;5 ， 這10個(gè)集合只能被分配{1;4;5;· ·· ; k ?1};{2;4;5;· ·· ; k ?1};{1;2;4;5;· ·· ; k ?1};{1;3;4;5;· ·· ; k ?1};{2;3;4;5;· ·· ; k ?1};{1;2;3;4;5;· ·· ; k ?1}這 6個(gè)集合 ， 不能區(qū)分xi; yj（i; j =1;2;3;4;5）這 10個(gè)頂點(diǎn) ， 矛盾.

由斷言5， 不妨設(shè){3};{4}不是 Z 中任一點(diǎn)的色集合 ， 由斷言1、2、4可知 ， {1};{2};{3};{4};{1;2}均不是任一點(diǎn)的色集合.下面考慮 C（xi） ， C（yj） ， i; j =1;2;3;4;5 ， 這10個(gè)集合互不相同 ， 且其中至少有 5個(gè)集合不屬于{?;{1};{2};{3};{4}} ， 不妨設(shè) C（x1） ， C（y1） ， C（y2） ， C（y3） ， C（y4）都不屬于{?;{1};{2};{3};{4}}. C（x1）不含1， 且不是 X 中任一點(diǎn)的色集合 ， C（yj）; j =1;2;3;4 ， 不含2， 且不是 Y 中任一點(diǎn)的色集合 .由于相鄰2 點(diǎn)的色集合之交非空 ， 故 C（x1）不是 Y ∪ Z 中任一點(diǎn)的色集合 ，? C（yj）; j =1;2;3;4 ， 不是 X ∪ Z 中任一點(diǎn)的色集合 ， 則 C（x1） ， C（y1） ， C（y2） ， C（y3） ， C（y4）均不是任一點(diǎn)的色集合. 因此{(lán)1};{2};{3};{4};{1;2} ， C（x1） ， C（y1） ， C（y2） ， C（y3） ， C（y4）這 10個(gè)集合互不相同 ， 且均不是任一點(diǎn)的色集合， 故p ?? （k i 1）? 10 ， 矛盾.

引理2? 當(dāng)k ?14且 ∑（k i 1）? 10< p ? ∑（i（k））? 10時(shí) ， K5;5;p 存在 k -VDIETC.

證明為了給出 K5;5;p 的 k-IE-全染色 ， 先對(duì) K5;5;p 的每個(gè)頂點(diǎn)對(duì)應(yīng) {1;2;· ·· ; k}的一個(gè)子集 ，令 D（x1）= {1;2;· ·· ; k}; D（x2）=D（x1）＼ {2}; D（x3）=D（x1）＼ {3}; D（x4）= D（x1）＼ {4}; D（x5）=D（x1）＼{5}; D（y1）=D（x1）＼{1}; D（y2）=D（x1）＼{6} ， D（y3）= D（x1）＼ {7} ， D（y4）=D（x1）＼ {8} ， D（y5）= D（x1）＼{9} ， D（zi）= {i +9} ， i=1;2;· ·· ; k ?9 ， D（zk? 8）= {1;10} ， D（zk? 7）= {2;10} ， D（zk? 6）= {3;10} ， D（zk? 5）= {4;10} ， D（zk? 4）= {5;10} ， D（zk? 3）= {6;10} ， D（zk? 2）= {7;10} ， D（zk? 1）= {8;10} ， D（zk）= {9;10}.

將除{1;2};{1;10}; {2;10}; {3;10}; {4;10}; {5;10}; {6;10}; {7;10}; {8;10}; {9;10}外的{1;2;· ·· ;k}的 2-子集 ， 3-子集 ， ·· ·; 11-子集排成一個(gè)序列 1. 令 D（zk+1） ， D（zk+2） ， ·· ·;? D（zp）依次是 1中的第1;2;· ·· ; p ? k 項(xiàng). 這一點(diǎn)是可以做到的 ， 因?yàn)?中含有（）+（）+· ·· +（） ?10項(xiàng) ， 而p ? k ?（ ）+（）+· ·· +（） ?10 ， 即p ?? （i（k））? 10.

下面給出 K5;5;p 的k -IE-全染色 g .令g（xi）= 1; g（yj）= 2（i; j =1;2;3;4;5）. 用max{D（zi）}染點(diǎn) zi ，i =1;2;· ·· ; p .

當(dāng)|D（zi）|= 2時(shí) ， g（uzi）= min{D（u）∩ D（zi）} ， u ∈ X ∪ Y ， i =1;2;· ·· ; p .

當(dāng)|D（zi）|= 3時(shí) ， g（uzi）= min{D（u）∩ D（zi）} ， u ∈{x2; x3; x4; x5; yj} ， g（x1zi）= min{D（x1）∩D（zi）＼{g（x2zi）; g（x3zi）; g（x4zi）; g（x5zi）; g（yjzi）}} ， i =1;2;· ·· ; p ， j =1;2;3;4;5 .

當(dāng)|D（zi）|= 4時(shí) ， g（uzi）= min{D（u）∩ D（zi）} ， u ∈{x3; x4; x5; yj} ， g（x2zi）= min{D（x2）∩ D（zi）＼{g（x3zi）; g（x4zi）; g（x5zi）; g（yjzi）}} ， g（x1zi）? =g（yjzi）}} ， i =1;2;· ·· ; p ， j =1;2;3;4;5 .FCD86179-7F39-4C2E-AD6D-ACE81DE4BD3A

當(dāng)|D（zi）|=5時(shí) ， g（uzi）= min{D（u）∩ D（zi）} ，min{D（x1）∩D（zi）＼{g（x2zi）; g（x3zi）; g（x4zi）; g（x5zi）;u ∈{x4; x5; yj} ， g（x3zi）= min{D（x3）∩ D（zi）＼ {g（x4zi）;g（x5zi）; g（yjzi）}} ， g（x2zi）= j（i）n{D（x2）∩ D（zi）＼{g（x3zi）; g（x4zi）; g（x5zi）; g（yjzi）}} ， g（x1zi）= j（i）n{D（x1）∩ D（zi）＼ {g（x2zi）; g（x3zi）; g（x4zi）; g（x5zi）; g（yjzi）}} ， i =1;2;· ·· ; p ， j =1;2;3;4;5 .

當(dāng)|D（zi）|=6 時(shí) ， g（uzi）=? min{D（u）∩ D（zi）} ，g（yjzi）}} ， g（x3zi） = j（i）n{D（x3）∩ D（zi）＼ {g（x4zi）;u ∈{x5; yj} ， g（x4zi）= min{D（x4）∩ D（zi）＼ {g（x5zi）;g（x5zi）; g（yjzi）}} ， g（x2zi） = min{D （x2）∩ D（zi）＼{g（x3zi）; g（x4zi）; g（x5zi）; g（yjzi）}} ， g（x1zi）= j（i）n{D（x1）∩ D（zi）＼ {g（x2zi）; g（x3zi）; g（x4zi）; g（x5zi）; g（yjzi）}} ， i =1;2;· ·· ; p ， j =1;2;3;4;5 .

當(dāng)|D（zi）|=7 時(shí) ， g（uzi）=? min{D（u）∩ D（zi）} ， u ∈{y1; y2; y3; y4; y5} ， g（x5zi）= min{D（x5）∩ D（zi）＼{g（yjzi）}} ， g（x4zi）= j（i）n{D（x4）∩D（zi）＼{g（x5zi）; g（yjzi）}} ， g（x3zi）= j（i）n{D（x3）∩D（zi）＼{g（x4zi）; g（x5zi）; g（yjzi）}} ， g（x2zi）=? j（i）n{D（x2）∩ D（zi）＼{g（x3zi）; g（x4zi）; g（x5zi）; g（yjzi）}} ， g（x1zi）=? j（i）n{D（x1）∩D（zi）＼{g（x2zi）; g（x3zi）; g（x4zi）; g（x5zi）; g（yjzi）}} ， i =1;2;· ·· ; p ， j =1;2;3;4;5 .

當(dāng)|D（zi）|=8時(shí) ， g（uzi）=min{D（u）∩D（zi）} ， u ∈{y2; y3; y4; y5} ， g（y1zi）=min{D（y1）∩ D（zi）＼{g（y2zi）;g（y3zi）; g（y4zi）; g（y5zi）}} ， g（x5zi）= j（i）n{D（x5）∩D（zi）＼{g（yjzi）}} ， g（x4zi）= j（i）n{D（x4）∩D（zi）＼{g（x5zi）; g（yjzi）}} ， g（x3zi）= j（i）n{D（x3）∩D（zi）＼{g（x4zi）; g（x5zi）; g（yjzi）}} ， g（x2zi）= j（i）n{D（x2）∩D（zi）＼{g（x3zi）; g（x4zi）; g（x5zi）; g（yjzi）}} ， g（x1zi）=? j（i）n{D（x1）∩D（zi）＼{g（x2zi）; g（x3zi）; g（x4zi）; g（x5zi）; g（yjzi）}} ， i =1;2;· ·· ; p ， j =1;2;3;4;5 .

當(dāng)|D（zi）|=9時(shí) ， g（uzi）=min{D（u）∩ D（zi）} ， u ∈{y3; y4; y5} ， g（y2zi）= min{D（y2）∩ D（zi）＼ {g（y3zi）;g（y4zi）; g（y5zi）}} ， D（zi）＼{g（yjzi）}} ， g（x5zi）; g（yjzi）}} ，g（y1zi）= min{D（y1）∩D（zi）＼{g（y2zi）; g（y3zi）; g（y4zi）; g（y5zi）}} ， g（x5zi）= min{D（x5）∩g（x4zi）= min{D（x4）∩D（zi）＼{g（x5zi）; g（yjzi）}} ， g（x3zi）=min{D（x3）∩D（zi）＼{g（x4zi）;g（x2zi）= min{D（x2）∩D（zi）＼{g（x3zi）; g（x4zi）; g（x5zi）; g（yjzi）}} ， g（x1zi）= min{D（x1）∩D（zi）＼ {g（x2zi）; g（x3zi）; g（x4zi）; g（x5zi）; g（yjzi）}} ， i =1;2;· ·· ; p ， j =1;2;3;4;5 .

當(dāng)|D（zi）|=10時(shí) ， g（uzi）= min{D（u）∩ D（zi）} ， u ∈{y4; y5} ， g（y3zi）= min{D（y3）∩ D（zi）＼ {g（y4zi）;g（y5zi）}} ， g（y2zi）= ?????? i（mi）n{D（y2）∩D（zi）＼{g（y3zi）; g（y4zi）; g（y5zi）}} ， g（y1zi）=????? i（mi）n{D（y1）∩D（zi）＼{g（y2zi）;g（y3zi）; g（y4zi）; g（y5zi）}} ， g（x5zi）= j（i）n{D（x5）∩D（zi）＼{g（yjzi）}} ， g（x4zi）= j（i）n{D（x4）∩D（zi）＼{g（x5zi）; g（yjzi）}} ， g（x3zi）= j（i）n{D（x3）∩D（zi）＼{g（x4zi）; g（x5zi）; g（yjzi）}} ， g（x2zi）= j（i）n{D（x2）∩D（zi）＼{g（x3zi）;g（x4zi）; g（x5zi）; g（yjzi）}} ， g（x1zi）= j（i）n{D（x1）∩ D（zi）＼{g（x2zi）; g（x3zi）; g（x4zi）; g（x5zi）; g（yjzi）}} ， i =1;2;· ·· ; p ， j =1;2;3;4;5 .FCD86179-7F39-4C2E-AD6D-ACE81DE4BD3A

當(dāng)|D（zi）|=11時(shí) ， g（y5zi）= min{D（y5）∩ D（zi）} ， g（y4zi）= min{D（y4）∩D（zi）＼ {g（y5zi）}} ， g（y3zi）=min{D（y3）∩D（zi）＼{g（y4zi）; g（y5zi）}} ， g（y2zi）= min{D（y2）∩D（zi）＼{g（y3zi）; g（y4zi）; g（y5zi）}} ， g（y1zi）=min{D（y1）∩D（zi）＼{g（y2zi）; g（y3zi）; g（y4zi）; g（y5zi）}} ， g（x5zi）= min{D（x5）∩D（zi）＼{g（yjzi）}} ， g（x4zi）=min{D（x4）∩D（zi）＼{g（x5zi）; g（yjzi）}} ， g（x3zi）= min{D（x3）∩D（zi）＼{g（x4zi）; g（x5zi）; g（yjzi）}} ， g（x2zi）=min{D（x2）∩ D（zi）＼ {g（x3zi）; g（x4zi）; g（x5zi）; g（yjzi）}} ， g（x1zi）= min{D（x1）∩ D（zi）＼ {g（x2zi）; g（x3zi）;g（x4zi）; g（x5zi）; g（yjzi）}} ， i =1;2;· ·· ; p ， j =1;2;3;4;5 .

用min{D（x）∩ D（y）}染邊xy ， ?x ∈ X;?y ∈ Y .

最后得到 K5;5;p 的k -IE-全染色g 是點(diǎn)可區(qū)別的 ， 因?yàn)?v ∈ V（K5;5;p） ， K5;5;p 均有C（v）= D（v）.

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

定理1

證明分以下幾種情況進(jìn)行討論.

情形1? 當(dāng)k ?14且 ∑（k i 1）? 10< p ? ∑（i（k））? 10時(shí)vt（ie）（K5;5;p）= k .

由引理1、引理2 可得結(jié)論成立.

情形2? 當(dāng)4 076? p ?8 167時(shí)vt（ie）（K5;5;p）= 13.

第1 步 ， 用反證法證明 K5;5;p 不存在12-VDIETC;第 2步具體構(gòu)造出13-VDIETC.假設(shè) K5;5;p 存在 12-VDIETC.

斷言1? ?a ∈{1;2;· ·· ;12} ， {a}不是 X ∪ Y 中任一點(diǎn)的色集合.

否則 ， 不妨設(shè)a =1 且C（x1）= {1} ， 則 Z 中每個(gè)點(diǎn)的色集合必含1， 故p ?， 矛盾.

斷言2任意2 -子集均不是 X ∪ Y 中任一點(diǎn)的色集合.

否則 ， 不妨設(shè) C（x1）= {1;2}且 g（x1）= 1. 此時(shí) Z 中每個(gè)點(diǎn)的色集合必含1 或2.在 {1;2;· ·· ;12}中 ， 含1 不含2 且最多含有11個(gè)元素的子集的個(gè)數(shù)為 （1i0）;含 2不含1 且最多含有11個(gè)元素的子集的個(gè)數(shù)為∑ （1i0）;同時(shí)含1 和2 且最多含有11個(gè)元素的子集的個(gè)數(shù)為∑ （1i0） ， 故p ?2 ∑（1i0）+ （1i0）+ 1= 3069 ， 矛盾.

斷言3? 任意3 -子集均不是 X ∪ Y 中任一點(diǎn)的色集合.

否則 ， 不妨設(shè) C（x1）= {1;2;3}且 g（x1）= 1. 此時(shí) Z 中每個(gè)點(diǎn)的色集合必含1，2或 3.在{1;2;· ·· ;12}中 ， 含1 不含2，3且最多含有11個(gè)元素的子集的個(gè)數(shù)為 （）;含 2不含1，3且最多含有11個(gè)元素的子集的個(gè)數(shù)為∑ （）;含 3不含1，2且最多含有11個(gè)元素的子集的個(gè)數(shù)為∑ （）;含 1，2不含3 且最多含有11個(gè)元素的子集的個(gè)數(shù)為∑ （）;含 1，3不含2 且最多含有11個(gè)元素的子集的個(gè)數(shù)為∑ （）;含2，3不含1 且最多含有11個(gè)元素的子集的個(gè)數(shù)為 （）;同時(shí)含1，2，3且最多含有11個(gè)元素的子集的個(gè)數(shù)為∑ （） ， 故p ? ∑（ ）+ 5∑ （） +∑ （） =3 581 ， 矛盾.

（1）當(dāng){g（xi）|i =1;2;3;4;5}∪ {g（yj）|j =1;2;3;4;5}里互不相同的顏色至少有3 種時(shí) ， 不妨設(shè){1;2;3}? {g（xi）|i =1;2;3;4;5}∪ {g（yj）|j =1;2;3;4;5}. 那么 {1};{2};{3};{1;2};{1;3};{2;3};{1;2;3}均不能作為 Z 中任一點(diǎn)的色集合 ， 由斷言1—3可知 ， {1};{2};{3};{1;2};{1;3};{2;3};{1;2;3}也均不是 X ∪ Y 中任一點(diǎn)的色集合， C（xi）{1;2;3} ， C（yj）{1;2;3} ， i; j =1;2;3;4;5 ， 且其中至少有3 個(gè)集合不屬于{{1};{2};{3};{1;2};{1;3};{2;3};?} ， 不妨設(shè)為 C（x1） ， C（y1） ， C（y2）.

1） C（x1）不是X 中任一點(diǎn)的色集合且 C（y1） ， C（y2）不是 Y 中任一點(diǎn)的色集合， 則10+p ?? （1i2）?10 ， 即p ?4 075 ， 矛盾.

2） C（x1）是 X 中點(diǎn)的色集合且 C（y1） ， C（y2）不是 Y 中任一點(diǎn)的色集合 ， 則{4};{5};· ·· ;{12}均不是任一點(diǎn)的色集合， 故10+p ?? （1i2）? 18 ， 即p ?4 067 ， 矛盾.

3） C（x1）是 X 中點(diǎn)的色集合且 C（y1） ， C（y2）中有1 個(gè)是 Y 中點(diǎn)的色集合 ， 則{4};{5};· ·· ;{12}均不是任一點(diǎn)的色集合， 故10+p ?? （1i2）? 17 ， 即p ?4 068 ， 矛盾.

4） C（x1） ， C（y1） ， C（y2）都是 X ∪ Y 中點(diǎn)的色集合 ， 則{4};{5};· ·· ;{12}均不是任一點(diǎn)的色集合 ，故10+p ?? （1i2）? 16 ， 即p ?4 069 ， 矛盾.FCD86179-7F39-4C2E-AD6D-ACE81DE4BD3A

（2）當(dāng) {g（xi）|i =1;2;3;4;5}∪ {g（yj）|j =1;2;3;4;5}里互不相同的顏色僅有2 種時(shí) ， 設(shè) g（xi）= 1; g（yj）= 2（i; j =1;2;3;4;5）.

斷言4? 在（2）下， {1};{2};{1;2}均不能作為 Z 中任一點(diǎn)的色集合.

斷言5? 在（2）下， {3};{4};{5};· ·· ;{12}中至少有2 個(gè)集合不是 Z 中任一點(diǎn)的色集合.

否則 ， 至多有1 個(gè)集合不是 Z 中任一點(diǎn)的色集合 ， 不妨設(shè){4};{5};· ·· ;{12}均是 Z 中任一點(diǎn)的色集合 ， 則 C（xi）∩ C（yj）? {4;5;· ·· ;12}; i; j =1;2;3;4;5 ， 此時(shí) C（xi）; C（yj）; i; j =1;2;3;4;5 ， 這10個(gè)集合只能被分配{1;4;5;· ·· ;12}; {2;4;5;· ·· ;12}; {1;2;4;5;· ·· ;12}; {1;3;4;5;· ·· ;12};{2;3;4;5;· ·· ;12};{1;2;3;4;5;· ·· ;12}這 6個(gè)集合 ， 不能區(qū)分xi; yj（i; j =1;2;3;4;5）這 10個(gè)頂點(diǎn) ， 矛盾.

由斷言5， 不妨設(shè){3};{4}不是 Z 中任一點(diǎn)的色集合 ， 由斷言1、2、4可知{1};{2};{3};{4};{1;2}均不是任一點(diǎn)的色集合.下面考慮 C（xi） ， C（yj） ， i; j =1;2;3;4;5 ， 這10個(gè)集合互不相同 ， 且至少有5 個(gè)不屬于 {?;{1};{2};{3};{4}} ， 不妨設(shè) C（x1） ，? C（y1） ，? C（y2） ，? C（y3） ，? C（y4）都不屬于{?;{1};{2};{3};{4}}. C（x1）不含1 且不是 X 中任一點(diǎn)的色集合 ， C（yj）; j =1;2;3;4 ， 不含2， 不是 Y 中任一點(diǎn)的色集合 ， 由于相鄰 2點(diǎn)的色集合之交非空 ， 故 C（x1）不是 Y ∪ Z 中任一點(diǎn)的色集合 ，? C（yj）; j =1;2;3;4 ， 不是 X ∪ Z 中任一點(diǎn)的色集合 ， 則 C（x1） ， C（y1） ， C（y2） ， C（y3） ， C（y4）均不是任一點(diǎn)的色集合 ， 因此{(lán)1};{2};{3};{4};{1;2} ， C（x1） ， C（y1） ， C（y2） ， C（y3） ， C（y4）這 10個(gè)集合互不相同 ， 且均不是任一點(diǎn)的色集合， 故10+p ?? （1i2）? 10 ， 即p ?4 075 ， 矛盾.

下面給出 K5;5;8167的 13-VDIETC.令 D（x1）= {1;2;· ·· ;13}; D（x2）= D（x1）＼ {2}; D（x3）= D（x1）＼{3}; D（x4）= D（x1）＼ {4}; D（x5）=D（x1）＼ {5}; D（y1）= D（x1）＼ {1}; D（y2）=D（x1）＼ {6} ， D（y3）= D（x1）＼{7} ， D（y4）= D（x1）＼ {8}; D（y5）= D（x1）＼ {9} ， 將除 {1;2};{1};{2};{3};{4};{5};{6};{7};{8};{9}外的{1;2;· ·· ;13}的其余1 -子集 ， 2-子集; ·· ·; 11-子集作為 Z 中點(diǎn)的色集合.據(jù)此可參照引理2 的證明過(guò)程中所述的染法給出 K5;5;8167的 13-VDIETC.當(dāng) 4076?p ?8 166時(shí) ，? K5;5;p 的13-VDIETC 可由? K5;5;8167的13-VDIETC 在 X ∪ Y ∪{z1; z2; ·· ·; zp}所導(dǎo)出的子圖上的限制給出.

情形3? 當(dāng)2 028? p ?4 075時(shí) ， vt（ie）（K5;5;p）= 12.

先用反證法證明 K5;5;p 不存在11-VDIETC.假如 K5;5;p 存在11-VDIETC.

斷言1? ?a ∈{1;2;· ·· ;11} ， {a}不是 X ∪ Y 中任一點(diǎn)的色集合.

否則 ， 不妨設(shè)a =1 且C（x1）= {1} ， 則 Z 中每個(gè)點(diǎn)的色集合必含1， 故p ? （1i0）= 1023 ， 矛盾.

斷言2? 任意2 -子集均不是 X ∪ Y 中任一點(diǎn)的色集合.

否則 ， 不妨設(shè) C（x1）= {1;2}且 g（x1）= 1. 此時(shí) Z 中每個(gè)點(diǎn)的色集合必含1 或2.在 {1;2;· ·· ;11}中 ， 含1 不含2 且最多含有11個(gè)元素的子集的個(gè)數(shù)為（ ）;含 2不含1 且最多含有11個(gè)元素的子集的個(gè)數(shù)為∑ （）;同時(shí)含 1和 2且最多含有 11個(gè)元素的子集的個(gè)數(shù)為∑ （） ， 故p ?2 ∑（ ）+ （） =1 534 ， 矛盾.

斷言3? 任意3 -子集均不是 X ∪ Y 中任一點(diǎn)的色集合.

否則 ， 不妨設(shè) C（x1）= {1;2;3}且 g（x1）= 1. 此時(shí) Z 中每個(gè)點(diǎn)的色集合必含1，2或 3.在 {1;2;· ·· ;11}中 ， 含1 不含2，3且最多含有11個(gè)元素的子集的個(gè)數(shù)為 （）;含 2不含1，3且最多含有11個(gè)元素的子集的個(gè)數(shù)為∑ （）;含 3不含1，2且最多含有11個(gè)元素的子集的個(gè)數(shù)為∑ （）;含 1，2不含3 且最多含有11個(gè)元素的子集的個(gè)數(shù)為∑ （）;含 1，3不含2 且最多含有11個(gè)元素的子集的個(gè)數(shù)為∑ （）;含2，3不含1 且最多含有11個(gè)元素的子集的個(gè)數(shù)為 （）;同時(shí)含1，2，3且最多含有11個(gè)元素的子集的個(gè)數(shù)為∑ （） ， 故p ?2 ∑（ ）+ 5∑ （） =1 790 ， 矛盾.FCD86179-7F39-4C2E-AD6D-ACE81DE4BD3A

（1）當(dāng) {g（xi）|i =1;2;3;4;5}∪ {g（yj）|j =1;2;3;4;5}里互不相同的顏色至少有 3種時(shí) ， 不妨設(shè){1;2;3}? {g（xi）|i =1;2;3;4;5}∪ {g（yj）|j =1;2;3;4;5}. 那么 {1};{2};{3};{1;2};{1;3};{2;3};{1;2;3}均不能作為 Z 中任一點(diǎn)的色集合 ， 由斷言1—3可知 ， {1};{2};{3};{1;2};{1;3};{2;3};{1;2;3}也均不是X ∪ Y 中任一點(diǎn)的色集合， C（xi）? {1;2;3} ， C（yj）? {1;2;3} ， i; j =1;2;3;4;5 ， 且至少有3 個(gè)不屬于{{1};{2};{3};{1;2};{1;3};{2;3};?}. 不妨設(shè)為 C（x1） ， C（y1） ， C（y2）.

1）當(dāng)? C（x1） ，? C（y1） ，? C（y2）都不是 X ∪ Y 中任一點(diǎn)的色集合時(shí) ， 有10+p ?? （1i1）? 10 ， 即p ?2 027 ， 矛盾.

2）當(dāng) C（x1） ， C（y1） ， C（y2）中只有1 個(gè)是 X ∪ Y 中點(diǎn)的色集合時(shí) ， 此時(shí){4};{5};· ·· ;{11}均不是任一點(diǎn)的色集合， 故10+p ?? （1i1）? 17 ， 即p ?2 020 ， 矛盾.

3）當(dāng) C（x1） ， C（y1） ， C（y2）中只有2 個(gè)是 X ∪ Y 中點(diǎn)的色集合時(shí) ， 此時(shí){4};{5};· ·· ;{11}均不是任一點(diǎn)的色集合， 故10+p ?? （1i1）? 16 ， 即p ?2 021 ， 矛盾.

4）當(dāng) C（x1） ， C（y1） ， C（y2）都是 X ∪ Y 中點(diǎn)的色集合時(shí) ， 此時(shí){4};{5};· ·· ;{11}均不是任一點(diǎn)的色集合， 故10+p ?? （1i1）? 15 ， 即p ?2 022 ， 矛盾.

（2）當(dāng) {g（xi）|i =1;2;3;4;5}∪ {g（yj）|j =1;2;3;4;5}里互不相同的顏色僅有2 種時(shí) ， 設(shè) g（xi）= 1; g（yj）= 2（i; j =1;2;3;4;5）.

斷言4? 在（2）下， {1};{2};{1;2}均不能作為 Z 中任一點(diǎn)的色集合.

斷言5? 在（2）下， {3};{4};{5};· ·· ;{11}中至少有2 個(gè)集合不是 Z 中任一點(diǎn)的色集合.

否則 ， 至多有1 個(gè)集合不是 Z 中任一點(diǎn)的色集合， 不妨設(shè){4};{5};· ·· ;{11}均是 Z 中任一點(diǎn)的色集合 ， 則 C（xi）∩ C（yj）? {4;5;· ·· ;11}; i; j =1;2;3;4;5 ， 此時(shí) C（xi）; C（yj）; i; j =1;2;3;4;5 ， 這10個(gè)集合只能被分配{1;4;5;· ·· ;11}; {2;4;5;· ·· ;11}; {1;2;4;5;· ·· ;11}; {1;3;4;5;· ·· ;11};{2;3;4;5;· ·· ;11};{1;2;3;4;5;· ·· ;11}這 6個(gè)集合 ， 不能區(qū)分xi; yj（i; j =1;2;3;4;5）這 10個(gè)頂點(diǎn) ， 矛盾.

由斷言5， 不妨設(shè){3};{4}不是 Z 中任一點(diǎn)的色集合 ， 由斷言1、2、4可知{1};{2};{3};{4};{1;2}均不是任一點(diǎn)的色集合.下面考慮 C（xi） ， C（yj） ， i; j =1;2;3;4;5 ， 這10個(gè)集合互不相同 ， 且至少有5 個(gè)不屬于{?;{1};{2};{3};{4}} ， 不妨設(shè) C（x1） ， C（y1） ， C（y2） ， C（y3） ， C（y4）都不屬于{?;{1};{2};{3};{4}}. C（x1）不含1， 不是 X 中任一點(diǎn)的色集合， C（yj）; j =1;2;3;4 ， 不含2， 不是 Y 中任一點(diǎn)的色集合.由于相鄰2 點(diǎn)的色集合之交非空 ， 故 C（x1）不是 Y ∪ Z 中任一點(diǎn)的色集合 ， C（yj）; j =1;2;3;4 ， 不是 X ∪ Z 中任一點(diǎn)的色集合， 則 C（x1） ， C（y1） ， C（y2） ， C（y3） ， C（y4）均不是任一點(diǎn)的色集合， 因此{(lán)1};{2};{3};{4};{1;2} ， C（x1） ， C（y1） ， C（y2） ， C（y3） ， C（y4）這 10個(gè)集合互不相同 ， 且均不是任一點(diǎn)的色集合， 故10+p ?? （1i1）? 10 ， 即p ?2 027 ， 矛盾.

下面給出 K5;5;4075的 12-VDIETC.令 D（x1）= {1;2;· ·· ;12}; D（x2）= D（x1）＼ {2}; D（x3）= D（x1）＼{3}; D（x4）= D（x1）＼ {4}; D（x5）=D（x1）＼ {5}; D（y1）= D（x1）＼ {1}; D（y2）= D（x1）＼ {6} ， D（y3）=D（x1）＼{7} ， D（y4）=D（x1）＼{8}; D（y5）= D（x1）＼{9} ， 將除{1;2};{1};{2};{3};{4};{5};{6};{7};{8};{9}外的{1;2;· ·· ;12}的其余1 -子集 ， 2-子集 ， ·· ·; 11-子集作為 Z 中任一點(diǎn)的色集合. 據(jù)此可參照引理2 的證明過(guò)程中所述的染法給出 K5;5;4075的 12-VDIETC.當(dāng) 2028?p ?4 074時(shí) ， K5;5;p 的12-VDIETC 可由 K5;5;4075的 12-VDIETC 在 X ∪ Y ∪{z1; z2; ·· ·; zp}所導(dǎo)出的子圖上的限制給出. 證畢.FCD86179-7F39-4C2E-AD6D-ACE81DE4BD3A

[參考文獻(xiàn)]

[1]HARARY? F，? PLANTHOLT? M. The? Point-Distinguishing? Chromatic? Index [M]//HARARY? F，? MAYBEE? J? S. Graphs? and Application. New York： Wiley Interscience， 1985：147-162.

[2]HOR??K M， SOT?K R. The fifth jump of the point-distinguishing chromatic index of Kn;n?? [J]. Ars Combinatoria， 1996， 42：233-242.

[3]HOR??K M， SOT?K R. Localization jumps of the point-distinguishing chromatic index of? Kn;n?? [J]. Discuss Math Graph Theory， 1997， 17：243-251.

[4]HOR??K M， ZAGAGLIA SALVI N. On the point-distinguishing chromatic index of Km;n?? [J]. Ars Combinatoria， 2006， 80：75-85.

[5]ZAGAGLIA SALVI N. On the value of the point-distinguishing chromatic index of Kn;n?? [J]. Ars Combinatoria， 1990， 29B：235-244.

[6]CHEN X E. Point-distinguishing chromatic index of the union of paths [J]. Czechoslovak Mathematical Journal， 2014， 64（3）：620-640.

[7]CHEN? X? E，? GAO? Y ?P，? YAO? B. Vertex-distinguishing? IE-total? colorings? of? complete? bipartite? graphs? Km;n（m < n）? [J]. Discussiones Mathematicae Graph Theory， 2013， 33（2）：289-306.

[8]LIU C J， ZHU E Q. General vertex-distinguishing total coloring of graphs [J]. Journal of Applied Mathematics， 2014：849748.

[9]牟亞蓉， 劉信生， 姚兵.基于含圈非連通圖優(yōu)美性的拓?fù)鋱D密碼[J].華東師范大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2020（1）：51-57.

[10]任韓， 吳昊.圖的空間理論：與圖有關(guān)的線性代數(shù)理論（下）[J].華東師范大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2012（6）：139-156.

[11]楊芳， 王治文， 陳祥恩， 等.完全圖和星的合成的點(diǎn)可區(qū)別正常邊染色[J].華東師范大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2013（5）：136-143.

[12]張爽. K2;n;p 的點(diǎn)可區(qū)別IE-全染色及一般全染色（2? n ?5; n ? p）? [D].蘭州：西北師范大學(xué)， 2020.

（責(zé)任編輯：陳麗貞）FCD86179-7F39-4C2E-AD6D-ACE81DE4BD3A