高度平面图的列表L（p，g）-标号.pdfVIP

第34卷 第3期 曲 阜 师 范 大 学 学 报 Vo1．34 No．3 2008年7月 Journal of Qufu Normal University July 2008 高度平面图的列表L(p，q)-标号 张苏梅， 马巧灵 (济南大学理学院，250022，山东省济南市 ) 摘要：如果平面图G的最大度△(G)=I (G)I—k，k=1，2，…，则称G为一个 图，k=1，2的hk-图称 为高度平面图．研究了高度平面图G的列表L(p，q)一标号问题，给出了高度平面图G的列表L(p，q)一标号数 A (G；p，q)的上界，并对hi-图证明了A (G；p，q)≤(2q—I)A+6(p—q)；对h2-图有 A (G；p，q)≤(2q—1)△+ 一 6q一1· ． 关键词：高度平面图；列表标号；列表标号数；最大度 中图分类号：O157，5 文献标识码：A 文章编号：1001-5337(2008)03-0042-05 1 引 言 本文中的图均指有限无向简单连通图．用E(G)，V(G)，F(G)，4(G)，6(G)(在不引起混淆的情况下，简 记为E， ，F，△，6)分别表示图G的边集、顶点集、面集、最大度和最小度，而I E(G)I，I V(G)I表示边数和顶 点数．用d ( )表示G中顶点(或面) 的度数，一个度为k的顶点(或面)，称做 一点( ．面)，用 (G)表示G 中 一点的集合．用Ⅳ。( )， ( )，Ⅳ ( )分别表示G中与顶点 相邻的顶点集、与顶点 不相邻的顶点集和 与顶点 距离为2的顶点集，用IⅣ。( )I，I ( )I，I ( )1分别表示上述点集中顶点的个数．对． 厂∈F(G)， 如果u。，u：，…，u 是依顺时针方向／的所有边界点，简记／=u。u：… ．对任意的 ，Y∈V(G)，dc( ，Y)表示顶 点 ，y之间的距离，其它未定义的符号见文献[1]． 定义1．1 设P，g是满足P≥g的正整数，z为非负整数集合 ：V(G)一z为一个映射，若对任意的 ，Y∈ V(G)，满足当dG( ，Y)=1时，有If( )-f(Y)I≥p；当dG( ，Y)=2时，有If( )一 Y)I≥g，则称／为G的一 个正常的L(p，g)一标号．图的一个k-L(p，g)一标号是指图的一个正常L(p，g)一标号，使得所有标号都不超过k， 即z={0，1，…，k}．称使G有一个k-L(p，g)一标号的最小k值为图G的L(p，g)一标号数，记为A(G；P，g)． 定义1．2 图G的一个列表 ，是指对G的每一个顶点 指定的一个标号集合 ( )．若G有一个正常 的L(p，g)一标号／，使得每一个顶点 满足f( )∈L( )，则称G是可列表L(p，g)一标号的．若G的所有顶点 的列表L( )的长度IL( )I=k+1，且G是可列表L(p，g)一标号的，则称G是可 一列表L(P，g)一标号的，定义 G的列表L(p，g)一标号数Af(G；p， )=rain{ I G有一个 一列表L(p，g)一标号}． 显然，当G中所有顶点 的列表L( )均为{0，1，2，…，k}时，k一列表L(P，g)．标号即为一般的 ．L(P， g)一标号，且A(G；p，g)≤Af(G；p，g)． 定义1．3 如果平面图G的最大度△(G)=I (G)I—k，k=1，2，…，则称G为一个hk-图，k=1，2的h ． 图称为高度平面图． 图的标号问题的研究背景是频率分配问题，即在几个不同地点的无线电发射台有效地分配无线电频率， 频率用非负整数表示，使得相近的地点分配到不同的频率，相邻的地点分配的频率至少相差2，从而使得这 些频率不会相互干扰．1980年Hale 将其归结为r，-染色问题；90年代Gerard，Chang和David Kuo 更精确 地将其归为L(2，1)标号问题，Griggs和Yeh 提出了著名猜想：对任意图G，L(2，1)．标号数A(G)≤△ ．近几