不含5-圈和6-圈的平面图的(2,1)-全标号

摘要

图G的(2,1)-全标号是对图G的顶点和边的一个标号分配,使得:(1)任意两个相邻顶点标号不同;(2)任意两条相邻边标号不同;(3)任意顶点与其相关联的边标号至少相差2.两个标号的最大差值称为跨度,图G的所有(2,1)-全标号的最小跨度称为(2,1)-全标号数,记为λT2(G).本文证明了如果G是一个△=p+5的平面图,且G不包含5-圈和6-圈,那么λT2(G)=2△-p,p=1,2,3.