Title | ||
---|---|---|
Improved upper bounds on the L(2,1) -labeling of the skew and converse skew product graphs |
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):v∈V(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. |
Year | DOI | Venue |
---|---|---|
2008 | 10.1016/j.tcs.2008.02.048 | Theoretical Computer Science |
Keywords | DocType | Volume |
Channel assignment,L(2,1)-labeling,Graph skew product,Graph converse skew product | Journal | 400 |
Issue | ISSN | Citations |
1 | 0304-3975 | 3 |
PageRank | References | Authors |
0.42 | 10 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Zhendong Shao | 1 | 67 | 8.60 |
David Zhang | 2 | 5068 | 234.25 |