Improved upper bounds on the L(2,1) -labeling of the skew and converse skew product graphs
- 作者：Zhendong Shao ; David Zhang
- 关键词：Channel assignment ; none ; color ; black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6V1G-4S020B9-1&_mathId=mml23&_user=1067359&_cdi=5674&_rdoc=16&_acct=C000050221&_version=1&_userid=10&md5=28d838e5831444d
- 刊名：Theoretical Computer Science
- 出版年：2008
- 期刊代码：114_03043975
- 类别：cp
- 出版时间：9 June 2008
- 卷：400
- 期：1-3
- 页码：230-233
- 文件大小：255 K
摘要
An L(2,1)-labeling of a graph G is a function f from the vertex set V(G) to the set of all nonnegative integers such that |f(x)−f(y)|≥2 if d(x,y)=1 and |f(x)−f(y)|≥1 if d(x,y)=2, where d(x,y) denotes the distance between x and y in 53c8af9bd0c75" title="Click to view the MathML source" alt="Click to view the MathML source">G. The L(2,1)-labeling number λ(G) of G is the smallest number k such that G has an L(2,1)-labeling with 53c508e0bc6e7f1e60" title="Click to view the MathML source" alt="Click to view the MathML source">max{f(v):v
V(G)}=k. Griggs and Yeh conjecture that λ(G)≤Δ2 for any simple graph with maximum degree c35c" title="Click to view the MathML source" alt="Click to view the MathML source">Δ≥2. This paper considers the graph formed by the skew product and the converse skew product of two graphs with a new approach on the analysis of adjacency matrices of the graphs as in [W.C. Shiu, Z. Shao, K.K. Poon, D. Zhang, A new approach to the L(2,1)-labeling of some products of graphs, IEEE Trans. Circuits Syst. II: Express Briefs (to appear)] and improves the previous upper bounds significantly.
V(G)}=k. Griggs and Yeh conjecture that λ(G)≤Δ2 for any simple graph with maximum degree c35c" title="Click to view the MathML source" alt="Click to view the MathML source">Δ≥2. This paper considers the graph formed by the skew product and the converse skew product of two graphs with a new approach on the analysis of adjacency matrices of the graphs as in [W.C. Shiu, Z. Shao, K.K. Poon, D. Zhang, A new approach to the L(2,1)-labeling of some products of graphs, IEEE Trans. Circuits Syst. II: Express Briefs (to appear)] and improves the previous upper bounds significantly.