Abstract | ||
---|---|---|
L(j,k)-labeling is a kind of generalization of the classical graph coloring motivated from a kind of frequency assignment problem in radio networks, in which adjacent vertices are assigned integers that are at least j apart, while vertices that are at distance two are assigned integers that are at least k apart. The span of an L(j,k)-labeling of a graph G is the difference between the maximum and the minimum integers assigned to its vertices. The L(j,k)-labeling number of G, denoted by @l"j","k(G), is the minimum span over all L(j,k)-labelings of G. Georges, Mauro and Whittlesey (1994) [1] established the relationship between @l"2","1(G) of a graph G and the path covering number of G^c (the complement of G). Georges, Mauro and Stein (2000) [2] determined the L(j,k)-labeling numbers of Cartesian products of two complete graphs. Lam, Lin and Wu (2007) [3] determined the @l"j","k-numbers of direct products of two complete graphs. In 2011, we (Wang and Lin, 2011 [4]) generalized the concept of the path covering to the t-group path covering of a graph where t(=1) is an integer and established the relationship between the L^'(d,1)-labeling number (d=2) of a graph G and the (d-1)-group path covering number of G^c. In this paper, we establish the relationship between the @l"j","k(G) of a graph G with diameter 2 and the @?j/k@?-group path coverings of G^c. Using those results, we can have shorter proofs to obtain the @l"j","k of the Cartesian products and direct products of complete graphs. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1016/j.ipl.2011.11.005 | Inf. Process. Lett. |
Keywords | Field | DocType |
group path,complete graph,cartesian product,direct product,minimum span,t-group path,graph g,classical graph,minimum integer,group path covering | Integer,Frequency assignment problem,Discrete mathematics,Graph,Combinatorics,Radio networks,Vertex (geometry),Cartesian product,Covering number,Mathematics,Graph coloring | Journal |
Volume | Issue | ISSN |
112 | 4 | 0020-0190 |
Citations | PageRank | References |
1 | 0.36 | 8 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Feng Wang | 1 | 38 | 7.16 |
Wensong Lin | 2 | 66 | 12.23 |