外部平面图的L(p,q)-标号

L(p,q)-Labelling of Outerplanar Graphs

对于正整数p,q,n与图G,如果函数φ:V(G)→｛0,1,2, ,n｝满足如下关系:若distG(u,v)=1,则|φ(u)-φ(v)|≥p;若distG(u,v)=2则|φ(u)-φ(v)|≥q,那么称函数φ为图G的L(p,q) 标号.在所有L(p,q) 标号中最小的n称为(p,q) 跨度,记作λ(G;p,q).本文证明了如下结论:设图G是一个最大度为Δ的外部平面图,那么λ(G;p,q)≤qΔ+4p+2q-4.

For integers p,q,n>0, a labelling of a graphφ:V(G)→｛0,1,2,…,n｝is called an L(p,q)-labelling if it satisfies:|φ(u)-φ(v)|≥p whenever and dist_G()(u,v)=1;|φ(u)-φ(v)|≥qwhenever dist_G()(u,v)=2. The (p,q)-span of a graph_G, denoted by λ(G;p,q), is the minimum n for which an L(p,q)-labelling exists. In this article we proved that: Let G be an outerplanar graph with maximal degree Δ, then. λ(G;p,q)≤qΔ+4p+2q-4.