运筹学学报 ›› 2010, Vol. 14 ›› Issue (3): 48-54.

• 运筹学 • 上一篇    下一篇

弦图的L(3,2,1)}-标号

袁万莲, 翟明清   

  • 出版日期:2010-09-15 发布日期:2010-09-15

YUAN Wan-Lian, DI Ming-Qing   

  • Online:2010-09-15 Published:2010-09-15

摘要: 图 G 的一个 L(3,2,1)- 标号是指从 V(G) 到非负整数集的一个映射 f, 满足: 当 d_G(u,v)=1 时, |f(u)-f(v)|\geq 3; 当 d_G(u,v)=2 时, |f(u)-f(v)|\geq 2; 当 d_G(u,v)=1 时, |f(u)-f(v)|\geq 1. L(3,2,1)-标号问题就是确定出最小的整数 \lambda_3(G) 使得 G存在最大标号不超过该数的 L(3,2,1)- 标号. 本文研究了弦图的 L(3,2,1)- 标号问题,获得了弦图及其一些子类, 如扇, r- 路,r- 树等的 \lambda_3 数的界.

Abstract: An L(3,2,1)-labeling of a graph G is a function from the vertex set V(G) to the set of all nonnegative integers such that |f(u)-f(v)|> 3 if d_G(u,v)=1,|f(u)-f(v)|> 2 if d_G(u,v)=2, and |f(u)-f(v)|> 1, if d_G(u,v)=3. The L(3,2,1)-labeling problem is to find the smallest number _3(G) such that there exists an L(3,2,1)-labeling function with no label greater than it. In this paper, we study this problem for chordal graphs. We obtain bounds of \lambda_3 number for chordal graphs and its subclasses, such as fan, r-path, r-tree and so on.