二部置换图的L(3,2,1)-标号  

The L(3,2,1)-labelings of Bipartite Permutation Graphs

作　　者：董晓媛[1] DONG Xiao-yuan(Nantong Normal College,Nantong 226000,China)

机构地区：[1]南通师范高等专科学校,江苏南通226000

出　　处：《数学的实践与认识》2021年第14期253-258,共6页Mathematics in Practice and Theory

基　　金：国家自然科学基金(11371207);江苏省高校自然科学面上项目(18KJD110009);校重点资助课题(TSGZ201806)。

摘　　要：任给一个图G,设函数f:V(G)→N,如果当d(x,y)=1时,有|f(x)-f(y)|≥3;当d(x,y)=2时,有|f(x)-f(y)|≥2;当d(x,y)=3时,有|f(x)-f(y)|≥1;则称f为图G的L(3,2,1)-标号.若一个L(3,2,1)-标号中的所有顶点的标号都不超过整数k,则称之为k-L(3,2,1)-标号.图G的L(3,2,1)-标号数,记作λ3,2,1(G),是使得图G存在k-L(3,2,1)-标号的最小的整数k.本文给出了二部置换图Hm,n的L(3,2,1)-标号数的界.当m=3时9≤λ3,2,1(F3,n)≤11;当3k-2≤m≤3k,k∈≥2时,2m+3≤λ3,2,1(Hm,n)≤15+12(k-2)+2=12k-7.An L(3,2,1)-labeling of a graph G is a function f from the vertex set of G to the set of all nonnegative integers such that for any two vertices u,vof G,|f(u)-f(v)≥4-dist(u,v),where dist(u,v)denotes the distance between uand v.A k-L(3,2,1)-labeling of G is one that no label is greater than k.The L(3,2,1)-labeling number of G,denoted byλ3,2,1(G)is the smallest k,such that G has a k-L(3,2,1)-labeling.In the paper we give bounds for the L(3,2,1)-labeling number of the bipartite permutation graph.

关 键 词：L(3 2 1)-标号 二部置换图 标号问题 

分 类 号：O157.5[理学—数学]