Labelling of Cactus Graphs

  • 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;
Keywords: Graph labelling, -labelling, cactus graph, frequency assignment, radiocoloring, design of algorithms, analysis of algorithms

References

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.

G J Chang and David Kuo, “The -labelling problem on graphs,” SIAM J. Discrete Math., vol. 9, pp. 309-316, 1996.

G J Chang and C Lu, “Distance two labelling of graphs,” European J. Combin., vol. 24, pp. 53-58, 2003.

S H Chiang and J H Yan, “On - labeling of Cartesian product of a path,” Discrete Appl. Math., vol. 156, pp. 2867-2881, 2008.

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.

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.

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.

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.

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.

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.

D Goncalves, “On the -labelling of graphs, In: EuroCom 2005, Discrete Math. and Theoretical Comput. Sci. Proc., vol. AE, pp. 81-86, 2005.

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.

W K Hale, “Frequency assignment: Theory and applications,” Proc. IEEE, vol. 68, pp. 1497-1514, 1980.

J Van den Heuvel and S McGuinnes, “Coloring the square of a planar graph,” J. Graph Theory, vol. 42, pp. 110-124, 2003.

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.

D Kral and R Skrekovski, “A theorem on channel assignment problem,” SIAM J. Discrete Math., vol. 16, pp. 426-437, 2003.

D D F Liu and R K Yeh, “On distance-two labellings of graphs,” Ars Combin., vol. 47, pp. 13-22, 1997.

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.

E M Reingold, J Nivergent and N Deo, Combinatorial algorithms: theory and practice, New Jersy: Prentice Hall, Inc., 1977.

D Sakai, “Labelling chordal graphs: Distance two condition,” SIAM J. Discret. Math., vol. 7, pp. 133-140, 1994.

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.

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.

R K Yeh, “Labelling graphs with a condition at distance two,” Ph. D. thesis, Department of Mathematics, University of South Carolina, Columbia, SC, 1990.

Published
2012-07-09
Section
Research Articles