Labeling bipartite permutation graphs with a condition at distance two
Labeling bipartite permutation graphs with a condition at distance two
复制标题
DOI：
10.1016/j.dam.2009.02.004
复制
发表时间：
2009-04
期刊：
影响因子：
--
通讯作者：
Toru Araki
中科院分区：
文献类型：
--
作者：
Toru Araki
图G的L（p，q）-标号是指图G的顶点到非负整数集合{0，1，.，λ}的赋值f，使得|f（u）−f（v）|如果u和v相邻，则≥p，并且|f（u）−f（v）|≥q，如果u和v相距2。G有L（p，q）-标号的λ的最小值记为λp，q（G）。L（p，q）标记问题与无线网络的信道分配问题有关。本文给出了一个计算二部置换图G的L（p，q）-标号的多项式时间算法，使得最大标号至多为（2 p −1）+q（bc（G）−2），其中bc（G）是G的偶团数.由于对任意二部图G，λp，q（G）≥p+q（bc（G）−2），上界至多为p−1，远离最优。
An L(p,q)-labeling of a graph G is an assignment f from vertices of G to the set of non-negative integers {0,1,…,λ} such that |f(u)−f(v)|≥p if u and v are adjacent, and |f(u)−f(v)|≥q if u and v are at distance 2 apart. The minimum value of λ for which G has L(p,q)-labeling is denoted by λp,q(G). The L(p,q)-labeling problem is related to the channel assignment problem for wireless networks. In this paper, we present a polynomial time algorithm for computing L(p,q)-labeling of a bipartite permutation graph G such that the largest label is at most (2p−1)+q(bc(G)−2), where bc(G) is the biclique number of G. Since λp,q(G)≥p+q(bc(G)−2) for any bipartite graph G, the upper bound is at most p−1 far from optimal.