Vol. 11 No. 4 (2012): Mapana Journal of Sciences
Research Articles

Labelling of Cactus Graphs

  • Nasreen Khan,
  • Madhumangal Pal,
  • Anita Pal
Nasreen Khan
Department of Mathematics, Global Institute of Management and Technology, Krishnagar-741102, West Bengal, India;
Madhumangal Pal
Department of Applied Mathematics with Oceanology and Computer Programming, Vidyasagar University, Midnapore-721102, West Bengal, India;
Anita Pal
Department of Mathematics, National Institute of Technology Durgapur, Durgapur-713209, West Bengal, India;
DOI: https://doi.org/10.12723/mjs.23.2

Published 2012-07-09

Keywords

  • Graph labelling,
  • -labelling,
  • cactus graph,
  • frequency assignment,
  • radiocoloring,
  • design of algorithms,
  • analysis of algorithms
    • ...More
    Less

Abstract

The -labelling of a graph is an abstraction of assigning integer frequencies to radio transmitters such that the transmitters that are one unit of distance apart receive frequencies that differ by at least two, and transmitters that are two units of distance apart receive frequencies that differ by at least one. The span of an -labelling is the difference between the largest and the smallest assigned frequency. The -labelling number of a graph , denoted by , is the least integer such that has an -labelling of span . A cactus graph is a connected graph in which every block is either an edge or a cycle. The goal of the problem is to show that for a cactus graph , where is the degree of . An optimal algorithm is also presented here to label the vertices of cactus graph using -labelling technique in time, where is the total number of vertices of the cactus graph.

References

  1. S S Adams, J Cass, M Tesch, D Sakai Troxell and C Wheeland, “The minimum span of - labeling of certain generalized Petersen graphs,” Disc. Appl. Math., vol. 155, pp. 1314-1325, 2007.
  2. G J Chang and David Kuo, “The -labelling problem on graphs,” SIAM J. Discrete Math., vol. 9, pp. 309-316, 1996.
  3. G J Chang and C Lu, “Distance two labelling of graphs,” European J. Combin., vol. 24, pp. 53-58, 2003.
  4. S H Chiang and J H Yan, “On - labeling of Cartesian product of a path,” Discrete Appl. Math., vol. 156, pp. 2867-2881, 2008.
  5. J P Georges, D W Mauro and M A Whittlesey, “Relating path covering to vertex labelings with a condition at distance two,” Discrete Math., vol. 135, pp. 103-111, 1994.
  6. J Georges and D W Mauro, “On the criticality of graphs labelled with a condition at distance two,” Congr. Numer., vol. 101, pp. 33-49, 1994.
  7. J Georges and D W Mauro, “On generalized Petersen graphs labelled with a condition at distance two,” Discrete Math., vol. 259, pp. 311-318, 2002.
  8. J Georges and D W Mauro, On regular graphs optimally labelled with condition at distance two, SIAM J. Discrete Math., vol. 17, pp. 320-331, 2003.
  9. J Georges, D W Mauro and M I Stein, “Labelling products of complete graphs with a condition at distance two,” SIAM J. Discrete Math., vol. 14, pp. 28- 35, 2000.
  10. J Georges, D W Mauro and M Whittlesey, “Relating path covering to vertex labelling with a condition of distance two,” Discrete Math., vol. 135, pp. 103-111, 1994.
  11. D Goncalves, “On the -labelling of graphs, In: EuroCom 2005, Discrete Math. and Theoretical Comput. Sci. Proc., vol. AE, pp. 81-86, 2005.
  12. J R Griggs and R K Yeh, “Labelling graphs with a condition at distance two,” SIAM J. Discrete Math., vol. 5, pp. 586-595, 1992.
  13. W K Hale, “Frequency assignment: Theory and applications,” Proc. IEEE, vol. 68, pp. 1497-1514, 1980.
  14. J Van den Heuvel and S McGuinnes, “Coloring the square of a planar graph,” J. Graph Theory, vol. 42, pp. 110-124, 2003.
  15. K Jonas, “Graph coloring analogue with a condition at distance two: L(2,1)-labellings and list -labellings,” Ph.D. Thesis, University of South Carolina, Columbia, 1993.
  16. D Kral and R Skrekovski, “A theorem on channel assignment problem,” SIAM J. Discrete Math., vol. 16, pp. 426-437, 2003.
  17. D D F Liu and R K Yeh, “On distance-two labellings of graphs,” Ars Combin., vol. 47, pp. 13-22, 1997.
  18. M Molloy and M R Salavatipour, “A bound on the chromatic number of the square of a planar graph,” J. Combin. Theory, Ser. B, vol. 94, pp. 189-213, 2005.
  19. E M Reingold, J Nivergent and N Deo, Combinatorial algorithms: theory and practice, New Jersy: Prentice Hall, Inc., 1977.
  20. D Sakai, “Labelling chordal graphs: Distance two condition,” SIAM J. Discret. Math., vol. 7, pp. 133-140, 1994.
  21. W F Wang and K W Lih, “Labelling planar graphs with conditions on girth and distance two,” SIAM J. Discrete Math., vol. 17, pp. 499-509, 2004.
  22. M A Whittlesey, J P Georges and D W Mauro, “On the -number of and related graphs,” SIAM J. Discrete Math., vol. 8, pp. 499-506, 1995.
  23. R K Yeh, “Labelling graphs with a condition at distance two,” Ph. D. thesis, Department of Mathematics, University of South Carolina, Columbia, SC, 1990.