Improved upper bounds on the L(2,1) -labeling of the skew and converse skew product graphs |
| |
Authors: | Zhendong Shao David Zhang |
| |
Affiliation: | aDepartment of Computer Science, The University of Western Ontario, London, ON, Canada;bBiometrics Research Centre, Department of Computing, Hong Kong Polytechnic University, Hong Kong |
| |
Abstract: | 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 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 max{f(v):vV(G)}=k. Griggs and Yeh conjecture that λ(G)≤Δ2 for any simple graph with maximum degree Δ≥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. |
| |
Keywords: | Channel assignment color:black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6V1G-4S020B9-1&_mathId=mml23&_user=10&_cdi=5674&_rdoc=16&_acct=C000053510&_version=1&_userid=1524097&md5=e1abace43f0c868f36b143a0691144e4" title="Click to view the MathML source" L(2" target="_blank">alt="Click to view the MathML source">L(2 1)-labeling Graph skew product Graph converse skew product |
本文献已被 ScienceDirect 等数据库收录! |
|