论文部分内容阅读
图的L(p，q)-标号来源于Hale所介绍的频率分配问题作为研究背景.给定图G和两个正整数p≥q.G的一个m-L(p，q)-标号是映射f：V(G)→{0，1，2，…，m}使得对任意x，y∈V(G)，若dG(x，y)=1则|f(x)-f(y)|≥p；若dG(x，y)=2则f(x)-f(y)|≥q.并称λp，q(G)=min{m|存在G的一个m-L(p，q)-标号}为图G的L(p，q)-数.
本学位论文，首先总结近些年图的L(p，q)-标号的主要结果和进展，然后我们兴趣在于最大度△(G)≤4的图G的线图L(G)的L(1，1)-标号和L(2，1)-标号.通常用λp,q(G)记线图L(G)的L(p，q)-数.最后，研究某些特殊图类的L(p,q)-标号问题.
线图L(G)的L(1，1)-标号是类似于图G的强边-染色，记Sx(G)(Sxl(G))为G的强边-色数(列表-强边-色数)，那么Sx(G)=λ1,1(G)+1.在1985年，Erd(o)s和Nesetril提出猜想，令G为简单图，那么当△(G)为偶数时，Sx(G)≤5△2(G)/4；当△(G)为奇数时，Sx(G)≤5△2(G)/4-△(G)/2+1/4.当△(G)=4时，猜想上界是20，Horák证明Sx(G)≤23.当△(G)=3时，猜想上界是10，这个界已被Anderson和Horák独立验证.
本文证明，当△(G)=4时，Sxl(G)≤22.而且，若围长g(G)≤4，则Sx(G)≤21.因为Sx(G)≤Sxl(G)，因此这个改进了先前Horák的结果.另外，若△(G)=3，则Sxl(G)≤11.
对于△(G)≤4的图G，Georges和Mauro证明λ2，1(G)≤2(△(G)-1)(△(G)+2).本文改进这个上界得到λ2,1(G)≤2△2(G)-2.
最后，本文研究k-退化图及G1和G2的M-matchedsum图G1M+G2的L(p，q)-数.特别的，给出仙人掌图，唯-圈图L(p，1)-数λp，1(G)的可达界.