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

作者：董晓媛

来源：数学的实践与认识, 2021, 51(14): 253-258.

• L(3,2,1)-标号
• 二部置换图
• 标号问题

任给一个图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.

• 单位
  南通师范高等专科学校