An L (0,1)-labelling of a graph G is an assignment of nonnegative integers to the vertices of G such that the difference between the labels assigned to any two adjacent vertices is at least zero and the difference between the labels assigned to any two vertices which are at distance two is at least one. The span of an L (0,1)-labelling is the maximum label number assigned to any vertex of G . The L (0,1)-labelling number of a graph G , denoted by λ 0.1 ( G ) is the least integer k such that G has an L (0,1)-labelling of span k . This labelling has an application to a computer code assignment problem. The task is to assign integer control codes to a network of computer stations with distance restrictions. A cactus graph is a connected graph in which every block is either an edge or a cycle. In this paper, we label the vertices of a cactus graph by L (0,1)-labelling and have shown that, △-1≤λ 0.1 ( G )≤△ for a cactus graph, where △ is the degree of the graph G .
W. K. Hale, “Frequency Assignment: Theory and Applications,” Proceedings of IEEE, Vol. 68, No. 12, 1980, pp. 1497-1514. doi:10.1109/PROC.1980.11899
A. A. Bertossi and M. A. Bonuccelli, “Code Assignment for Hidden Terminal Interference Avoidance in Multihope Packet Radio Networks,” IEEE/ACM Transactions on Networking, Vol. 3, No. 4, 1995, pp. 441-449. doi:10.1109/90.413218
X. T. Jin and R. K. Yeh, “Graph Distance-Dependent Labelling Related to Code Assignment in Computer Networks,” Naval Research Logistics, Vol. 51, 2004, pp. 159-164.
T. Makansi, “Transmitter-Oriented Code Assignment for Multihop Packet Radio,” IEEE Transactions on Communications, Vol. 35, No. 12, 1987, pp. 1379-1382. doi:10.1109/TCOM.1987.1096728
J. P. Georges and D. W. Mauro, “Generalized Vertex Labeling with a Condition at Distance Two,” Congressus Numerantium, Vol. 140, 1995, pp. 141-159.
A. A. Bertossi, M. C. Pinotti and R. Rizzi, “Channel Assignment on Strongly-Simplicial Graphs,” IEEE Proceedings of International Parallel and Distributed Processing Symposium (IPDPS’03), Nice, 22-26 April 2003, pp. 22-26.
H. L. Bodlaender, T. Kloks, R. B. Tan and J. Van Leeuwen, “Approximations for λ-Colorings of Graphs,” The Computer Journal, Vol. 47, No. 2, 2004, pp. 193-204. doi:10.1093/comjnl/47.2.193
T. Calamoneri, “The L (h, k)-Labelling Problem: A Survey and Annotated Bibliography,” The Computer Journal, Vol. 49, No. 5, 2009, pp. 585-630. doi:10.1093/comjnl/bxl018
P. J. Wan, “Wear-Optimal Conflict-Free Channel Set Assignments for an Optical Cluster-Based Hypercube Network,” Journal of Combinatorial Optimization, Vol. 1, 1997, pp. 179-186. doi:10.1023/A:1009759916586
N. Alon and B. Mohar, “The Chromatic Number of Graph Powers,” Combinatorics, Probability and Computing, Vol. 11, No. 1, 2002, pp. 1-10. doi:10.1017/S0963548301004965
S. H. Chiang and J. H. Yan, “On L (d, 1)-Labeling of Cartesian Product of a Path,” Discrete Applied Mathematics, Vol. 156, No. 15, 2008, pp. 2867-2881. doi:10.1016/j.dam.2007.11.019
J. R. Griggs and R. K. Yeh, “Labeling Graphs with a Condition at Distance 2,” SIAM Journal on Discrete Mathematics, Vol. 5, No. 4, 1992, pp. 586-595. doi:10.1137/0405048
R. K. Yeh, “Labeling Graphs with a Condition at Distance Two,” Ph.D Thesis, University of South Carolina, Columbia, 1990.
D. Kral and R. Skrekovski, “A Theorem on Channel Assignment Problem,” SIAM Journal on Discrete Mathematics, Vol. 16, No. 3, 2003, pp. 426-437. doi:10.1137/S0895480101399449
D. Goncalves, “On the L (p,1)-Labelling of Graphs, in: EuroCom 2005,” Discrete Mathematics and Theoretical Computer Science Proceedings, Vol. AE, 2005, pp. 81-86.
J. Van den Heuvel and S. McGuinnes, “Coloring the Square of a Plannar Graph,” Journal of Graph Theory, Vol. 42, No. 2, 2003, pp. 110-124. doi:10.1002/jgt.10077
M. Molloy and M. R. Salavatipour, “A Bound on the Chromatic Number of the Square of a Planar Graph,” Journal of Combinatorial Theory, Series B, Vol. 94, No. 2, 2005, pp. 189-213. doi:10.1016/j.jctb.2004.12.005
W. F. Wang and K. W. Lih, “Labelling Planar Graphs with Conditions on Girth and Distance Two,” SIAM Journal on Discrete Mathematics, Vol. 17, 2004, pp. 499-509.
N. Khan, A. Pal and M. Pal, “ L (2,1)-Labelling of Cactus Graphs,” Communicated.
S. S. Adams, J. Cass, M. Tesch, D. S. Troxell and C. Wheeland, “The Minimum Span of L (2,1)-Labeling of Certain Generalized Petersen Graphs,” Discrete Applied Mathematics, Vol. 155, No. 1, 2007, pp. 1314-1325. doi:10.1016/j.dam.2006.12.001
G. J. Chang, W. T. Ke, D. Kuo, D. D. F. Lin and R. K. Yeh, “On L (d,1)-Labellings of Graphs,” Discrete Mathematics, Vol. 220, 2000, pp. 57-66. doi:10.1016/S0012-365X(99)00400-8
G. J. Chang and C. Lu, “Distance Two Labelling of Graphs,” European Journal of Combinatorics, Vol. 24, 2003, pp. 53-58. doi:10.1016/S0195-6698(02)00134-8
J. Fiala, T. Kloks and J. Kratochvil, “Fixed-Parameter Complexity of λ-Labelling,” Discrete Applied Mathematics, Vol. 133, No. 1, 2001, pp. 59-72. doi:10.1016/S0166-218X(00)00387-5
J. Georges and D. W. Mauro, “On Generalized Petersen Graphs Labelled with a Condition at Distance Two,” Discrete Mathematics, Vol. 259, No. 1-3, 2002, pp. 311-318. doi:10.1016/S0012-365X(02)00302-3
J. Georges, D. W. Mauro and M. I. Stein, “Labelling Products of Complete Graphs with a Condition at Distance Two,” SIAM Journal on Discrete Mathematics, Vol. 14, 2000, pp. 28-35. doi:10.1137/S0895480199351859
P. K. Jha, “Optimal L (2,1)-Labelling of Cartesian Products of Cycles with an Application to Independent Domination,” IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications, Vol. 47, No. 10, 2000, pp. 1531-1534. doi:10.1109/81.886984
S. Klavzar and A. Vesel, “Computing Graph Invariants on Rotagraphs Using Dynamic Algorithm Approach: The Case of L (2,1)-Colorings and Independence Numbers,” Discrete Applied Mathematics, Vol. 129, 2003, pp. 449-460. doi:10.1016/S0166-218X(02)00597-8
D. Kuo and J. H. Yan, “On L (2,1)-Labelling of Cartesian Products of Paths and Cycles,” Discrete Mathematics, Vol. 283, No. 1-3, 2004, pp. 137-144. doi:10.1016/j.disc.2003.11.009
C. Schwarz and D. S. Troxell, “ L (2,1)-Labelling of Products of Two Cycles,” Discrete Applied Mathematics, Vol. 154, No. 1-3, 2006, pp. 1522-1540. doi:10.1016/j.dam.2005.12.006
R. K. Yeh, “The Edge Span of Distance Two Labelling of Graphs,” Taiwanese Journal of Mathematics, Vol. 4, No. 4, 2000, pp. 675-683.
R. Battiti, A. A. Bertossi and M. A. Bonuccelli, “Assigning Code in Wireless Networks: Bounds and Scaling Properties,” Wireless Networks, Vol. 5, No. 3, 1999, pp. 195-209. doi:10.1023/A:1019146910724