论文部分内容阅读
图的(p，1)—全标号对无线电频道分配问题具有现实意义。(p，1)—标号相当于对集合V(G)∪E(G)进行整数标号使邻的两点标不同的整数，相邻的两边标不同的整数，相关联的一点和一边的标号相差至少p.一个(p，1)—全标号的跨度是指两个标号之间的最大差值。图G的(p，1)—全数λтp(G)是指图G的(p，1)—全标号的最小跨度。本论文研究关于图的(p，1)—全标号的问题，指出了[1]中关于偶完全图的(p，1)—全标号其中一个定理的错误证明；还证明了关于几乎完全图的(p，1)—全标号与完全图的(p，1)—全标号的关系；研究给出了完全k元树和星图的(p，1)—全标号，轮图的(2，1)—全标号，以及研究了双圈图的(p，1)—全标号，给出了双圈图的构造元图的(p，1)—全标号，猜想对于双圈图，△+p—1≤λтp≤△+p+1。