考虑含有完全图K4的图的补图的L（2，1）-标号的岛序列＊

雒金梅，余 航，任树鑫，郭海防

（西安工业大学 北方信息工程学院，西安710200）

L（2，1）-标号，由Griggs和Roberts提出的，是产生于各种频率分配问题的一个顶点标号问题，目的是找到最小的频率使用范围，同时确保充分靠近的两个传输机分配到的传输频率的差不小于一个给定的正数［1-2］．L（p，q）-标号是图G 的顶点集到整数集的一个映射，并且满足任意两个相邻的顶点的标号差至少为p，任意两个距离为2的顶点标号差至少为q，若p＝2，q＝1那么L（p，q）-标号就是著名的L（2，1）-标号，它是L（p，q）-标号的一种特殊情况．关于L（p，q）-标号，一些专家已经对某些特殊的简单图做了研究，特别是对L（2，1）-标号进行了讨论．对任意的图，文献［3］研究了图变量λ（G）和图G的其他图变量，如图G的色数χ（G），最大度Δ＝Δ（G）之间的关系，已经得到各种类型的图的λ数，如树，圈，路，3-连通图．文献［4］研究了弦图的λ数．另外文献［5］研究了λ（G）、图变量c（GC）（图G的补图的路覆盖数）及图G的顶点数之间的关系．L（2，1）-标号的推广已经在研究．文献［6-9］证明了当c（GC）≥2，λ（G）＝n＋c（GC）-2，其中n为图G的顶点数，给出了路覆盖的一个更一般的结果的完全证明，证明了图G的补图的一个路覆盖导出了G的一个有c（GC）-1个洞的λ（G）标号．文献［10］提出了ρ（G）≥1，导出两个不同岛序列的λ（G）标号的连通图的存在性，证明了2-稀疏数的补图是容许至少两个不同岛序列的连通图．文中给出了另一类图的λ数和洞指数ρ（G）的关系，路覆盖数和L（2，1）-标号的岛序列，研究某类含有完全图K4的图的路覆盖数，以期在两种最小路覆盖之下均证明其补图的两个不同的λ标号导出的两个岛序列不同．

1 L（2，1）-标号的相关知识

L（2，1）-标号问题是类似于频率分配问题的顶点标号问题．图G的一个L（2，1）-标号是从G的顶点集V（G）到非负整数集｛0，1，…，k｝的一个函数f，并且满足：若d（x，y）＝1，则｜f（x）-f（y）｜≥2，若d（x，y）＝2，则｜f（x）-f（y）｜≥1．其中d（x，y）表示顶点x和顶点y之间的距离．这些标号问题已经被用来模仿无线电分配问题［3］．图G的使用集合｛0，1，…，k｝（未必是所有的元素）中的元素进行标号的一个L（2，1）-标号叫做一个k标号．使得G有一个k标号的最小的k叫做G的λ数，用λ（G）来表示．一个λ（G）标号简记为λ标号．称一个k标号有洞h（0＜h＜k），若h在这个标号中没有被使用．G的所有λ（G）标号的洞的个数的最小值叫做G的洞指数，用ρ（G）来表示．不难看出，若一个λ（G）标号恰有ρ（G）个洞，那么任意两个洞是不连续的［2］．一个有ρ（G）个洞的图G的一个给定λ标号的岛是指用于标号的连续整数的极大集合．一个有ρ（G）个洞的图G的一个给定λ标号的岛序列是指岛基数按不减顺序的有序排列（这个定义允许基数重复）．

定义1 图G的一个路覆盖是G中包含G的所有顶点的点不交的路的集合．

图G的路覆盖数用c（G）来表示，是G的具有最少路数的一个路覆盖中路的数目．恰有c（G）条路的一个路覆盖叫做G的最小路覆盖．

定义2 图G的一个轻点为度不大于2的点，重点为G中度大于2的点．

图G的一个藤S定义为G中的一条极大路且满足一个端点是叶子点，其余点在G中为轻点．

为了书写方便，用GC表示图G的补图．

引理1［1］G是一个有n个顶点的图，那么c（GC）≥2当且仅当λ（G）＝n＋c（GC）-2．

引理2［1］G是一个有n个顶点的图，且λ（G）≥n-1，那么ρ（G）＝c（GC）-1．

2 图G路覆盖与补图GC的岛序列

引理3 设G为含有完全图K4且图中除K4中外没有相邻的重点，e为图中与两个轻点关联的一条边，若e∉K4，那么e包含在G的每个最小路覆盖中．

证明 设u和w为与e关联的两个轻点．假设存在G的不包含e的一个最小路覆盖，因为u和w为轻点，那么在这个最小路覆盖中存在着以u为端点的路P和以w为端点的路Q，并且边e既不在P中，也不在Q中，由于e∉K4，P和Q是不同的，因此P＋Q＋e是一条路．用P＋Q＋e取代原来的路P和Q，得到了有路数更少的G的一个路覆盖，与假设这个路覆盖为最小路覆盖矛盾，因此e包含在G的每个最小路覆盖中．

引理4 G是有m（m ≥1）条边，n个顶点，p（≥2）个叶子点的某类含有完全图K4的图（且G中除K4外不含相邻的重点）．那么c（G）＝p．

证明 由于p≥2，对p用归纳法．

p＝2时，由于G中含有完全图K4，c（G）＝2＝p．

p＞2时，假设图G中含有k（2≤k＜p）个叶子点时结论成立．

设S为G中的与重点v关联的藤，则G-S为有p-1个叶子点的图，由归纳假设，c（G-S）＝p-1，若把S增加到G-S的任一个有p-1条路的最小路覆盖中，得到了图G的含有p条路的路覆盖．所以c（G）≤p．

假设c（G）≤p-1．考虑图G的任一个最小路覆盖．

由于S是这个最小路覆盖中某条路P′的子图，若v∉P′，则P′＝S．把S从这个最小路覆盖中删除，得到了G-S的有c（G）-1≤p-2条路的路覆盖，与c（G-S）＝p-1矛盾．所以v∈P′，且v为P′的中间点，设e为P′中与v和S关联的边，f为与v关联的另一条边且f∉P′，则与f关联的另一个点u必为轻点，那么u一定是G中的最小路覆盖中某条不同于P′的路Q的端点，用S来代替P′，用Q＋P′-S-e来代替Q，得到了有c（G）条路的另一个最小路覆盖，把S从G中删除，得到了G-S的有c（G）-1≤p-2条路的最小路覆盖．与c（G-S）＝p-1矛盾．

综上所述c（G）＝p，得证．

定理1 G是一个有m（m≥1）条边，n个顶点，p（≥2）个叶子点，含有完全图K4且图中除K4中外没有相邻的重点那么GC容许至少两个不同的岛序列．

证明 由于p≥2，通过对p进行归纳来证明．

当p＝2时，c（G）＝p＝2，c（G）≥2

由引理1有λ（GC）＝n＋c（G）-2＝n＋2-2＝n．

由引理2有ρ（GC）＝c（G）-1＝2-1＝1

① 两个叶子点悬挂在不同的重点．图1给出了图G 的两个最小路覆盖（P1，P2）和（P3，P4），其中P1为以两个叶子点为端点的最长路，P1＝u1u2，…，ul1，P2＝v1v2，…，vl2；P3＝x1x2，…，xl3，P4＝y1y2，…，yl4．

图1 最小路覆盖（P1，P2）和（P3，P4）Fig．1 Minmum path covering（P1，P2）and（P3，P4）

这两个最小路覆盖导出了GC的恰有ρ（GC）＝1个洞的两个λ（GC）-标号f1和f2，其中

由于l1＝n-1，l2＝1，1＜l3＜l1因此由f1导出的的岛序列不同于由f2导出的岛序列，故GC容许两个不同的岛序列．

②两个叶子点悬挂在同一个重点．图2给出了图G 的两个最小路覆盖（P1′，P2′）和（P3′，P4′）

图2 最小路覆盖（P1′，P2′）和（P3′，P4′）Fig．2 Minmum path covering（P1′，P2′）and（P3′，P4′）

这两个最小路覆盖导出了GC的恰有ρ（GC）＝1个洞的两个λ（GC）-标号f1′和f2′，

若l1′ ＜l2′，则l4′ ＜l1′ ＜l2′ ＜l3′．则λ（GC）-标号f1′ 导出的GC的岛序列为（l1′，l2′），由标号f2′ 导 出 的GC的 岛 序 列 为 （l4′，l3′），显 然 （l1′，l2′）不 同 于（l4′，l3′）．

若l1′≥l2′且l1′≤l3′，则l4′≤l2′≤l1′≤l3′，λ（GC）-标号f1′导出的GC的岛序列（l2′，l1′）不同于f2′ 导出的GC的岛 序列（l4′，l3′）．

若l1′ ≥l2′ 且l1′ ＞l3′，则 由 于l3′ ＞l2′，故 有l1′ ＞l3′ ＞l2′．又 由 于l1′ ＋l2′ ＝l3′ ＋l4′，所 以λ（GC）-标号f1′ 导出的GC的岛序列为（l2′，l1′），f2′ 导 出 的GC的 岛 序 列 为 （l4′，l3′）或 （l3′，l4′），显然 （l2′，l1′）不 同 于 （l4′，l3′）或（l3′，l4′）．

由f1′导出的岛序列不同于由f2′导出的岛序列，从而GC容许两个不同的岛序列．

所以p＝2时，GC容许两个不同的岛序列．

假设p＞2，对每个有k（2≤k＜p）个叶子点含有完全图K4且图中除K4中外没有相邻的重点的图G，GC容许至少两个不同的岛序列．

考虑任意一个有p（＞2）个叶子点的图G，选择G的一个藤S，则G-S为有p-1≥2个叶子点的满足假设条件的图，根据归纳假设，H ＝（G-S）容许两个不同的岛序列．设g1和g2为H的有ρ（H）个洞、导出两个不同岛序列的λ（H）标号，把这两个标号延拓到S＝v1v2…vs，通过给vi（i＝1，2，…，s）分配标号λ（H）＋i＋1，这两个新的标号即为GC的有ρ（H）＋1个洞的（λ（H）＋s＋1）-标号．

因此GC容许两个不同的岛序列．

定理2 G是一有p（p≥2）个叶子点的含有完全图K4且图中除K4中外没有相邻的重点，则GC是连通的．

当u和z在GC中相邻时，显然成立．

假设u和z在GC中不相邻．由于v1，v2为G中的叶子点，所以u和z中至少有一个顶点在GC中与vi（i＝1，2）相邻．若u和z在GC中都与某个vi相邻，则uviz即为GC中连通u和z的路．若u和v1在GC中相邻，z和v2在GC中相邻，由于v1，v2为G中的叶子点，且图G不为路，所以v1，v2在G中必不相邻，则在GC中必相邻，从而uv1v2z即为GC中连通u和z的路．

若u和z中恰有一点个在GC中与vi（i＝1，2）相邻，而另一个点在G中与vi（i＝1，2）相邻．不失一般性，假设u在GC中与vi（i＝1，2）相邻，z在G中与vi（i＝1，2）相邻，v1，v2为G中的叶子点，所以vi（i＝1，2）在GC中与除z以外的所有点相邻．由于G为双圈2-稀疏连通图且G中至少有一个圈中的顶点个数多于3，故存在一个顶点w且w∉｛u，z，v1，v2｝，使得w在GC中与z相邻，显然vi（i＝1，2）与w在GC中相邻，所以uv1wz即为G中连通u和z的路．

综上，GC是连通的，证毕．

3 结论

文中研究了含有完全图K4且图中除K4中外没有相邻的重点的一类图的两种最小路覆盖，通过考虑这类图的路覆盖数和它的补图的L（2，1）-标号下λ数和洞指数ρ（G）之间的关系，得到了它的补图的两个不同的L（2，1）-标号容许两个不同的岛序列，最后证明了它的补图的连通性．

［1］ ADAMS S S，TRAZKOVICH A，TROXELL D S，et al．On the Island Sequences of Labelings with a Condition at Distance Two［J］．Disc Appl Math，2010（158）：1．

［2］ GRIGGS J R，YEH R K．Labeling Graph with a Condition at Distance Two［J］．Siam J Disc Math，2005（19）：585．

［3］ GEORGES J P，MAURO D W．On the Structure of Graphs with Non-Surjective L（2，1）-Labelings［J］．Siam J Disc Math，2005（19）：208．

［4］ SAKAI T．No-hole K-tupe（r＋1）-Distant Colorings，Discrete［J］．Appl Math，1996（64）：67．

［5］ GEORGES J P，MAURO D W，WHITTLESEY M A．Relating Path Coverings to Vertex Labelings with a Condition at Distance Two ［J］．Disc Math，1994（135）：103．

［6］ HALE W K．Frequency Assignment［J］．Theory and Applications Proc，1980（68）：1497．

［7］ CALAMONERI T．The L（h，k）-labeling Problem：A Survey and Annotated Bibliography［J］．Computer Journal，2006，49（5）：585．

［8］ GEORGES J P，MAURO D W．A Note on Collections of Graphs with Non-Surjective Lambda Labelings［J］．Discrete Appl Math，2005，46（1）：92．

［9］ CHANG G J，KUO D．The L（2，1）-Labelling Problem on Graphs，SIAM ［J］．Discrete Math，1996（9）：309．

［10］ GEORGES J P，MAURO D W，STEIN M I．Labelling Products of Complete Graphs with a Condition at Distance Two［J］．Siam J Disc Math ，2000（14）：28．