一類整數距離圖的點蔭度

徐 莉，左連翠

（天津師范大學 數學科學學院，天津 300387）

一類整數距離圖的點蔭度

徐 莉，左連翠

（天津師范大學 數學科學學院，天津 300387）

整數距離圖以全體整數作為頂點集，頂點u、v相鄰當且僅當u－v∈D，其中D是一個正整數集.對于m＞3，令Dm＝［1，m］＼［1，3］.本研究得到了G（Dm）的點蔭度.

整數距離圖；點蔭度；樹染色；正常染色；點色數

1 預備知識

引理2 假設有3個點b1＜b2＜b3在圖G（Dm）的一個樹染色中染了同一種顏色，則有

1）若存在一條同色（b1，b2）－路，則b3∈｛b1＋i，b2＋i｜i∈［1，3］｝或者b3≥b1＋（m＋1）；

2）若存在一條同色（b1，b3）－路，并且b3－b1≤m，則b2∈｛b1＋i，b3－i｜i∈［1，3］｝；

3）若存在一條同色（b2，b3）－路，則b1∈｛b2－i，b3－i｜i∈［1，3］｝或者b1≥b3－（m＋1）.

證明 1）否則，若b3?｛b1＋i，b2＋i｜i∈［1，3］｝，并且b3＜b1＋（m＋1），則b1b3、b2b3∈E（G），從而（b1，b2）－路和2條邊b1b3、b2b3形成一個圈，矛盾.2）和3）同理可證.引理證畢.

若6個點vi（i∈［0，5］）染了同色β，且滿足：v2－v1＝v3－v2＝v4－v3＝1，min｛v1－v0，v5－v4｝≤2，v1－v0、v5－v4∈［1，3］，v5－v0∈［5，7］，則這樣的一個集合｛vi｜i∈［0，5］｝稱為一個由β和v0決定的F－型集.在不引起混淆的情況下，簡稱為F－型集.

引理3 若Vβ是一個由β和v0決定的F－型集，則在G（Dm）的一個樹著色f中，對任意i∈［6，m＋4］＼｛vj｜j∈［0，5］｝，有f（v0＋i）≠β.

證明 否則，設對于某個i∈［6，m＋4］＼｛vj｜j∈［0，5］｝，有f（v0＋i）＝β.因為v0＝v與v4和v5都相鄰，則由引理2，有v＋i∈｛v4＋j，v5＋j｜j∈［1，3］｝或者v＋i≥v4＋（m＋1）.因為m≥8，所以v0、v5、v1、v＋i導出一個4－圈，或者v1、v5、v2、v＋i導出一個4－圈，或者v2、v5、v3、v＋i導出一個4－圈，或者v0、v5、vj、v＋i、v4導出一個5－圈（其中j∈［1，3］），或者v＋i≥v4＋（m＋1）.從而v＋i≥v＋m＋4，這是不可能的.引理證畢.

引理4 在G（Dm）的樹著色f中，若頂點a0＜a1＜…＜a5得到同色，且a5－a0≤m，則｛ai｜i∈［0，5］｝是一個F－型集.

證明 顯然，若下列斷言成立，則引理得證.

斷言1a0a4、a0a5、a1a5∈E（G）.顯然有 min｛a4－a0，a5－a1｝≥4，從而a0a4、a0a5、a1a5∈E（G）.

斷言2a2－a1＝a3－a2＝a4－a3＝1.假若 max｛a2－a1，a3－a2，a4－a3｝≠1，則由斷言1可知，a0、a4、a1、a5導出一個4－圈，矛盾.從而斷言2成立.

斷言3a1－a0、a5－a4∈［1，3］.若a1－a0＞3，則由斷言2可知a0、a1、a5導出一個三角形，矛盾.因此a1－a0∈［1，3］.同理可證a5－a4∈［1，3］.

斷言4a1－a0＋a5－a4≤4.否則，即a1－a0＋a5－a4≥5，由斷言3有a1－a0＝3或者a5－a4＝3，那么a0、a2、a5導出一個三角形，或者a0、a3、a5導出一個三角形，矛盾.

綜上，｛ai｜i∈［0，5］｝是一個F－型集.引理證畢.

引理5 在G（Dm）的樹著色f中，若頂點0≤a0＜a1＜…＜a6≤m＋4著同色，則對于i＝0、1，有ai＋5－ai＞m.

證明 假設a5－a0≤m，則由引理4知，｛ai｜i∈［0，5］｝是一個F－型集，因此a0a4、a0a5、a1a5∈E（G），且由a6－a4≤m及引理2知a6∈｛a5＋i｜i∈［1，3］｝，那么a0、a5、a1、a6導出一個4－圈，或者a0、a4、a6、a5

2 G（Dm）的點蔭度

斷言a0＝0，a1＝1，a3＝m＋1，a4＝m＋2，a5＝m＋3且a6＝m＋4.

通過2個子斷言來證明該斷言.

子斷言1a0＝0，a1＝1，a5＝m＋3且a6＝m＋4.

1）設a5＝m＋1.則由引理5知，a0a4∈E（H）且a0＝0.進而有a3∈｛a0＋i，a4－i｜i∈［1，3］｝.

若a3∈｛a0＋i｜i∈［1，3］｝，則a3＝3且a1a5、a2a5、a3a5∈E（H），那么a4＝4或者a4∈｛a5－i｜i∈［1，3］｝.若a4＝4，則有a4a5、a4a6∈E（H），從而a3a6?E（H），即a6＝m＋4.此時由引理5知，在H中有n－1種顏色染［5，m］∪［m＋2，m＋3］中的m－2個點，使得每一種顏色恰染滿足v5－v0≤7的6個點v0（≥5）、v1、v1＋1、v1＋2、v1＋3、v5.那么由引理4知，頂點m＋8、m＋9只能染α色，而它們與a5、a6導出一個4－圈，矛盾.若a4∈｛a5－i｜i∈［1，3］｝，則a4≥m－2，從而a1a4、a1a5、a2a4、a2a5∈E（H），即頂點a1、a4、a2、a5導出一個4－圈，矛盾.

若a3∈｛a4－i｜i∈［1，3］｝＼｛a0＋i｜i∈［1，3］｝，則a3≥4，a4－a3≤3，且a0a3∈E（H），故由引理2知a4∈｛a6－i｜i∈［1，3］｝.因為a1≤3且m≥8，所以a4≥m＋1，并且a1a4、a1a5∈E（H），從而a3a5?E（H），a3≥m－2.進而a1a3?E（H）（否則，頂點a0、a3、a1、a4導出一個4－圈），那么a3－a1≤3，故a1≥a3－3≥m－5＝3.由此可得m＝8，a3＝6且a5＝9.從而a0a2、a2a5∈E（H），所以頂點a0、a2、a5、a1、a4導出一個5－圈，矛盾.

2）假設a5＝m＋2.那么a0＝0（否則，若a0＝1，則可以對a0，a1，…，a6通過一個單位“轉換”像1）一樣得出矛盾）.

2.1）若a4＝m＋1，則由a1≤3可知a1a4∈E（H）.那么a3∈｛a1＋i，a4－i｜i∈［1，3］｝.

當a3∈｛a1＋i｜i∈［1，3］｝時，若a1≥2，則a1a5∈E（H），那么由引理2知a2≥m－2，從而a0a2、a0a3、a1a3∈E（H），且a2＝m－1（否則，頂點a0、a2、a5、a1、a3導出一個5－圈，矛盾），所以頂點a0、a2、a1、a3導出一個4－圈，矛盾.若a1＝1，則a3≤4，故a2a4、a2a5、a3a4、a3a5∈E（H），即a2、a4、a3、a5導出一個4－圈，也推出矛盾.

當a3∈｛a4－i｜i∈［1，3］｝時，即a3≥m－2時，有a0a3、a1a3∈E（H）（若a1a3?E（H），則a1≥m－5＝3，m＝8，且由引理5可知a6＝m＋4，故頂點a0、a2、a6、a3導出一個4－圈，矛盾）.由引理2知a2≤a1＋3，那么頂點a0、a2、a4、a1、a3導出一個5－圈（若a2∈［4，5］），或者a1、a3、a5、a2、a4導出一個5－圈（若a2＝3），或者a0、a2、a5、a1、a3導出一個5－圈（若a2＝6），也推出矛盾.

2.2）若a4≤m，則a0a4∈E（H），那么由引理2有a3≤3或者a3≥a4－3成立.若a3≤3，則a3＝3且a2＝2，從而a4≤6（否則，頂點a2、a3都和頂點a4、a5相鄰，它們導出一個4－圈，矛盾），所以a4a5∈E（H），故由a2a5∈E（H）可知a4∈［4，5］.那么a4a6∈E（H）且a6＝m＋4（否則，a6＝m＋3，頂點a3、a5、a4、a6導出一個4－圈，矛盾）.不失一般性，假設a4＝5.此時H中共有n－1種顏色染m－2個頂點4，6，…，m＋1，m＋3，使得每一種顏色恰染6個滿足v5－v0≤7的頂點v0（≥4）、v1、v1＋1、v1＋2、v1＋3、v5，且v1＋3≥9.由引理4～6知，頂點m＋8、m＋9必染α色，但它們與a5、a6一起導出一個4－圈，矛盾.若a3≥a4－3，則a3a4?E（H），并假設a0a3∈E（H），從而a3≥4.若a3＞a1＋3，則a1a3∈E（H）且頂點a0、a3、a1、a4導出一個4－圈，矛盾.從而a3≤a1＋3≤6，故a2a5、a3a5、a3a6∈E（H），那么由引理2知，a4≤a6－3，即a4＝m，a6＝m＋3，a3≥m－3，a1a4∈E（G），從而a1a5、a1a3∈E（H）（否則，頂點a0、a3、a5、a1、a4導出一個5－圈，或者頂點a0、a3、a1、a4導出一個4－圈）.所以a1＝1，a3＝4，與a3a4?E（H）矛盾.

總之，可得a5＝m＋3，從而a6＝m＋4.

由a0、a1與a5、a6在H中的對稱性可得a0＝0且a1＝1.

子斷言2a3＝m＋1且a4＝m＋2.

若a3≤m，則a3＝3或者a0a3∈E（G）.

1）假設a3＝3，則a2＝2，a3a5∈E（G），從而a4∈｛a3＋i，a5－i｜i∈［1，3］｝.當a4∈｛a3＋i｜i∈［1，3］｝時，4≤a4≤6，那么a4a5、a4a6∈E（G）.共有n－1種顏色染［4，a4－1］∪［a4＋1，m＋2］中的m－2個點，由引理4～6知，每一種顏色恰染滿足條件v5－v0≤7的6個頂點（4≤）v0、v1、v1＋1、v1＋2、v1＋3、v5（≤m＋2），從而m＋8必染α色，但它與a5、a4、a6導出一個圈，矛盾.

當a4∈｛a5－i｜i∈［1，3］｝且a3a4∈E（G）時，a4a5?E（G），那么a4≥m.令a4＝m＋i，其中i∈［0，2］.共有n－1種顏色染［4，a4－1］∪［a4＋1，m＋2］中的m－2個點，由引理4～6知，每一種顏色恰染滿足條件v5－v0≤7的6個點（4≤）v0、v1、v1＋1、v1＋2、v1＋3、v5（≤m＋2），那么由引理6知，點m＋7必染α色，但它與a4、a3、a5導出一個4－圈，矛盾.

2）假設a0a3∈E（G）.那么m≥a3≥4且a3a6∈E（G），從而有a4∈｛a3＋i｜i∈［1，3］｝或者a4∈｛a6－i｜i∈［1，3］｝.

2.1）若a4∈｛a3＋i｜i∈［1，3］｝，則a3≥m＋2且a4≥m＋1（否則，a4＜m，則a0a4、a4a6∈E（H），那么頂點a0、a3、a6、a4導出一個4－圈，矛盾）.① 假設a4＝m＋1，那么a1a4、a1a3∈E（H）.若a2a3∈E（H），則a2a4∈E（H），故頂點a1、a3、a2、a4導出一個4－圈，矛盾.從而a3－a2≤3且a2≥a3－3≥m－5≥3.若a2＝3，則有m＝8且a3＝6，那么a1a3、a3a5、a2a5、a2a4、a1a4∈E（H），即頂點a1、a3、a5、a2、a4導出一個5－圈，矛盾.所以a2＞3，從而頂點a0、a2、a6、a3導出一個4－圈，也推出矛盾.② 假設a4＝m＋2，那么a3≥m－1，故a1a3∈E（H）.若a2＞4，則頂點a0、a2、a6、a3導出一個4－圈，矛盾.故a2≤3，a2a3、a2a4∈E（G）.令a2＝i，其中i∈［2，3］，a3＝j∈［m－1，m］，那么共有n－1種顏色染H的頂點子集［2，m＋1］＼［i，j］中的m－2個點，使得每一種顏色恰染滿足條件v5－v0≤7的6個點（2≤）v0＜v1、v1＋1、v1＋2、v1＋3＜v5（≤m＋1）.由引理6知，點m＋6必染α色，但它與a3、a2、a4導出一個4－圈，矛盾.

2.2）若a4∈｛a6－i｜i∈［1，3］｝，假設a3a4∈E（H），那么a4≥m＋1且4≤a3≤a4－4.顯然，a2a4、a3a5∈E（G），故a2a3、a2a5?E（G），那么a2＝2且4≤a3≤5.令a3＝i，其中i∈［4，5］，并令a4＝j，其中j∈［m＋1，m＋2］.共有n－1種顏色染H中m－2個點［3，m＋2］＼｛i，j｝，使得每一種顏色恰染滿足條件v5－v0≤7的6個點（3≤）v0＜v1、v1＋1、v1＋2、v1＋3＜v5（≤m＋2）.從而點m＋7必染α色，但它與a4、a3、a5導出一個圈，矛盾.

綜上可得，a3＝m＋1，那么a4＝m＋2.從而斷言成立.

若4≤a2≤m－3，則頂點a1、a2、a3導出一個3－圈，矛盾.從而有a2≤4或者a2≥m－2.若a2≤4，則a2a3、a2a4∈E（H）.共有n－1種顏色染H中m－2個點［2，m］＼｛a2｝，由引理4～6知，每一種顏色恰染滿足條件v5－v0≤7的6個點（2≤）v0＜v1、v1＋1、v1＋2、v1＋3＜v5（≤m），由引理6知，頂點m＋6必染α色，但它與a4、a2、a3導出一個圈，矛盾.若a2≥m－2，則a1a2、a1a3∈E（H）.同樣只有n－1種顏色染H中m－2個點［2，m］＼｛a2｝，由引理4～6知，每一種顏色恰染滿足條件v5－v0≤7的6個點（2≤）v0＜v1、v1＋1、v1＋2、v1＋3＜v5（≤m）.那么頂點m＋5必染α色，但它與a3、a1、a2導出一個4－圈，亦推出矛盾.

［1］ CATLIN P A，LAI H J.Vertex arboricity and maximum degree［J］.Discrete Mathematics，1995，141：37－46.

［2］ ˇSKREKOVSKI R.On the critical point－arboricity graphs［J］.J Graph Theory，2002，39：50－61.

［3］ EGGLETON R B，ERD?S P，SKILTON D K.Colouring the real line［J］.J Combin Theory：Ser B，1985，39：86－100.

［4］ CHANG G J，LIU D F，ZHU X D.Distance graphs and T－coloring［J］.J Combin Theory：Ser B，1999，75：259－269.

［5］ YU Q L，ZUO L C.The fractional vertex arboricity of graphs［J］.Lecture Notes in Computer Science，2007（1）：245－252.

［6］ ZUO L C，YU Q，WU J L.Vertex aboricity of integer distance graphG（Dm，k）［J］.Discrete Mathematics，2009，309：1649－1657.

Vertex arboricity of a class of integer distance graphs

XULi，ZUOLian－cui
（College of Mathematical Science，Tianjin Normal University，Tianjin 300387，China）

An integer distance graph is a graph with all integers as vertex set，and two verticesu，v∈Zare adjacent if and only if－v∈Dwhere the distance setDis a subset of the positive integer set.LetDm＝［1，m］＼［1，3］form＞3，the vertex arboricity of the integer distance graphG（Dm）is obtained.

integer distance graph；vertex arboricity；tree coloring；proper coloring；chromatic number

O157.5

A

1671－1114（2012）03－0013－05

2011－11－15

天津師范大學引進人才科研啟動基金資助項目（5RL066）

徐 莉（1988—），女，碩士研究生.

左連翠（1964—），女，教授，主要從事圖論及其應用方面的研究.

（責任編校 馬新光）