L(1,1)-Labeling of Direct Product of any Path and cycle
DOI:
https://doi.org/10.4067/S0716-09172014000400002Keywords:
L(1, 1)-labeling, D-2 coloring, direct product of graphs, cross product of graphs, path and cycle, etiquetado L(1, 1), coloreado D-2, producto directo de grafos, producto cruz de grafos, recorrido y ciclo.Abstract
Suppose that [n] = {0, 1, 2,...,n} is a set of non-negative integers and h,k G [n].The L (h, k)-labeling of graph G is the function l : V(G) — [n] such that |l(u) — l(v)| > h if the distance d(u,v) between u and v is 1 and |l(u) — l(v)| > k if d(u,v) = 2. Let L(V(G)) = {l(v): v G V(G)} and let p be the maximum value of L(V(G)). Then p is called Xi^—number of G if p is the least possible member of [n] such that G maintains an L(h, k) — labeling. In this paper, we establish X} — numbers of Pm X Pn and Pm X Cn graphs for all m,n > 2.References
[1] Bertossi, A. A. and Bonuccelli, M. A. Code Assignment for Hidden Terminal Interference Avoidance in multiloop Pocket Radio Networks. IEEE/ACM Trans. on Networking 3,(4), pp. 441-449, (1995).
[2] Berttiti, R., Bertossi, A. A. and Bonuccelli, M. A. Assigning Codes in Wireless networks: Bounds and Scaling Properties. Wirel. Netw., 5, pp. 441-449, (1999).
[3] Calamonerri, T. The L(h, k)-Labeling Problem: A Updated Survey and Annoted Bibliography. The Computer Journal 54(8), pp.1344
1371, (2011).
[4] Calamonerri, T., Pelc, A., and Petreschi, R. Labeling Trees with a Condition at Distance Two. Discrete Math. 306, pp. 1534-1539, (2006).
[5] Chang, G. J. and Kuo, D. The L(2, 1)-Labeling of Graphs SIAM J. Discrete math. 9, pp. 309-316, (1996).
[6] Chang, G. J., Ke, W.-T, Kuo, D. A., Liu, D. D.-F and Yeh, R. K. (d, 1)-Labeling of Graphs. Discrete Math. 220, pp. 57-66, (2000).
[7] Chiang,S.-H and Yan, J.-H. On L(d, 1)-labeling of Cartesian product of a cycle and a path. Discrete App. Math 156, pp. 2867-2881, (2008).
[8] Georges, J. P, and Mauro, D.W. Generalized Vertex Labeling with a Condition at Distance Two. Congr. Numer., 109, pp. 141-159, (1995).
[9] Georges, J. P, Mauro, D. W. and Stein, M. I. Labeling Products of Complete Graphs with a Condition at Distance Two. SIAM J. Discrete Math. 14, pp. 28-35, (2000).
[10] Georges, J. P, Mauro, D. W. On Regular Graphs Optimally labeled with a Condition at Distance Two. SIAM J. Discrete Math. 17 (2), pp. 320-331, (2003).
[11] Goncalves, D. L(p — 1)—Labellings of Graphs. Discrete Math. 308, pp. 1405-1414, (2008)
[12] Gravier, S., Klavzer, S. and Mollard M., Codes and L(2, 1)—Labeling in Sierpinski Graphs. Taiwan. J. math. 4, pp. 671-681, (2004).
[13] Griggs, J. R., Yeh, R. K. Labeling Graph with a condition at Distance Two. SIAM J. Discrete Math. 5, pp. 586-595, (1992).
[14] Hale, W. K. Frequency Assignment: Theory and Application. Proc. IEEE 68, pp. 1497-1514, (1980).
[15] Jha, P. K, Klavzer, S. and Vessel, A. L(2, 1)—Labeling of Direct Product of Paths and Cycles. Discrete Applied Math. 145 (2), pp. 141-159, (2005).
[16] Kral, D. and Skrekovski, R. A. Theorem About the Channel Assignment J. Discrete Math. 16 (3), pp. 426-437, (2003).
[17] Kuo, D. and Yan, J.-H. On L(2, 1)—Labeling of Cartesian Product of Two Cycles. Discrete Math. 283, pp. 137-144, (2004).
[18] Sakai, T. D. Chordal Graphs with a Condition at Distance Two. SIAM J. Discrete Math. 7, pp. 133-140, (1994).
[19] Schwartz, C. and Sakai, T. D. L(2, 1)—Labeling of Product of Two Cycles. Discrete Applied Math. 154, pp. 1522-1540, (2006).
[20] Sopena, E., Wu, J. Coloring the square of the Cartesian product of two Cycles Graphs with a Condition at Distance Two. Discrete Math. 310, pp. 2327-2333, (2010).
[21] Wensong, D. and Peter C.,L. Distance Two Labeling and Direct Product of Graphs. Discrete Math. 308, pp. 3805-3815, (2008).
[22] Weichsel, P. M. The Kronecker Product of Graphs. Proc. Amer. Math. Soc. 13 1962; 47 — 62
[23] Whittlessey, M. A, Georges, J. P. and Mauro, D. W. On the λ—number of Qn and Related Graphs. SIAM J. Discrete Math. 8, pp. 499-506, (1995).
[2] Berttiti, R., Bertossi, A. A. and Bonuccelli, M. A. Assigning Codes in Wireless networks: Bounds and Scaling Properties. Wirel. Netw., 5, pp. 441-449, (1999).
[3] Calamonerri, T. The L(h, k)-Labeling Problem: A Updated Survey and Annoted Bibliography. The Computer Journal 54(8), pp.1344
1371, (2011).
[4] Calamonerri, T., Pelc, A., and Petreschi, R. Labeling Trees with a Condition at Distance Two. Discrete Math. 306, pp. 1534-1539, (2006).
[5] Chang, G. J. and Kuo, D. The L(2, 1)-Labeling of Graphs SIAM J. Discrete math. 9, pp. 309-316, (1996).
[6] Chang, G. J., Ke, W.-T, Kuo, D. A., Liu, D. D.-F and Yeh, R. K. (d, 1)-Labeling of Graphs. Discrete Math. 220, pp. 57-66, (2000).
[7] Chiang,S.-H and Yan, J.-H. On L(d, 1)-labeling of Cartesian product of a cycle and a path. Discrete App. Math 156, pp. 2867-2881, (2008).
[8] Georges, J. P, and Mauro, D.W. Generalized Vertex Labeling with a Condition at Distance Two. Congr. Numer., 109, pp. 141-159, (1995).
[9] Georges, J. P, Mauro, D. W. and Stein, M. I. Labeling Products of Complete Graphs with a Condition at Distance Two. SIAM J. Discrete Math. 14, pp. 28-35, (2000).
[10] Georges, J. P, Mauro, D. W. On Regular Graphs Optimally labeled with a Condition at Distance Two. SIAM J. Discrete Math. 17 (2), pp. 320-331, (2003).
[11] Goncalves, D. L(p — 1)—Labellings of Graphs. Discrete Math. 308, pp. 1405-1414, (2008)
[12] Gravier, S., Klavzer, S. and Mollard M., Codes and L(2, 1)—Labeling in Sierpinski Graphs. Taiwan. J. math. 4, pp. 671-681, (2004).
[13] Griggs, J. R., Yeh, R. K. Labeling Graph with a condition at Distance Two. SIAM J. Discrete Math. 5, pp. 586-595, (1992).
[14] Hale, W. K. Frequency Assignment: Theory and Application. Proc. IEEE 68, pp. 1497-1514, (1980).
[15] Jha, P. K, Klavzer, S. and Vessel, A. L(2, 1)—Labeling of Direct Product of Paths and Cycles. Discrete Applied Math. 145 (2), pp. 141-159, (2005).
[16] Kral, D. and Skrekovski, R. A. Theorem About the Channel Assignment J. Discrete Math. 16 (3), pp. 426-437, (2003).
[17] Kuo, D. and Yan, J.-H. On L(2, 1)—Labeling of Cartesian Product of Two Cycles. Discrete Math. 283, pp. 137-144, (2004).
[18] Sakai, T. D. Chordal Graphs with a Condition at Distance Two. SIAM J. Discrete Math. 7, pp. 133-140, (1994).
[19] Schwartz, C. and Sakai, T. D. L(2, 1)—Labeling of Product of Two Cycles. Discrete Applied Math. 154, pp. 1522-1540, (2006).
[20] Sopena, E., Wu, J. Coloring the square of the Cartesian product of two Cycles Graphs with a Condition at Distance Two. Discrete Math. 310, pp. 2327-2333, (2010).
[21] Wensong, D. and Peter C.,L. Distance Two Labeling and Direct Product of Graphs. Discrete Math. 308, pp. 3805-3815, (2008).
[22] Weichsel, P. M. The Kronecker Product of Graphs. Proc. Amer. Math. Soc. 13 1962; 47 — 62
[23] Whittlessey, M. A, Georges, J. P. and Mauro, D. W. On the λ—number of Qn and Related Graphs. SIAM J. Discrete Math. 8, pp. 499-506, (1995).
Published
2017-03-23
How to Cite
[1]
D. Olayide Ajayi and C. Adefokun, “L(1,1)-Labeling of Direct Product of any Path and cycle”, Proyecciones (Antofagasta, On line), vol. 33, no. 4, pp. 369-388, Mar. 2017.
Issue
Section
Artículos
-
Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.
