Open Neighborhood Coloring of Prisms

Geetha Kempanapura Nanjunda Swamy; Kyathsandra Nagendra Rao Meera; Narahari Narasimha Swamy; Badekara Sooryanarayana

doi:10.5614/j.math.fund.sci.2013.45.3.4

Authors

Geetha Kempanapura Nanjunda Swamy Department of Mathematics, Amrita School of Engineering
Kyathsandra Nagendra Rao Meera Department of Mathematics, Amrita School of Engineering
Narahari Narasimha Swamy Department of Mathematics, University College of Science, Tumkur University
Badekara Sooryanarayana Department of Mathematical and Computational Studies, Dr. Ambedkar Institute of Technology

DOI:

https://doi.org/10.5614/j.math.fund.sci.2013.45.3.4

Keywords:

coloring, labeling, neighbor, open neighborhood, prism.

Abstract

For a simple, connected, undirected graph G(V, E) an open neighborhood coloring of the graph G is a mapping f : V (G) --> Z+ such that for each w in V(G), and for all u, v in N(w), f(u) is different from f(v). The maximum value of f(w), for all w in V (G) is called the span of the open neighborhood coloring f. The minimum value of span of f over all open neighborhood colorings f is called open neighborhood chromatic number of G, denoted by Xonc(G). In this paper we determine the open neighborhood chromatic number of prisms.

References

Buckley, F. & Harary, F., Distance in Graphs, Addison-Wesley, New York, United States, 1990.

Harary, F., Graph Theory, New Delhi, India, Narosa Publishing House, 1969.

Hartsfield, N. & Ringel, G., Pearls in Graph Theory, Boston, United States, Academic Press, 1994.

Calamoneri, T., The L(h,k)-labeling Problem: A Survey and Annotated Bibiliography, The Computer Journal, 49, pp. 585-608, 2006.

Kuo, D. & Yan, J-H., On L(2,1) Labelings of Carteisan Product of Paths and Cycles, Discrete Mathematics, 283, pp.137-144, 2004.

Chang, G.J. & Kuo, D., The L(2,1) Labeling Problem on Graphs, SIAM Journal of Discrete Mathematics, 9(2), pp.309-316, May 1996.

Chang, G.J., Ke, W-T, Kuo, D., Liu, D. D-F. & Yeh, R.K., On L(d,1) Labelings Graphs , Discrete Mathematics, 220, pp. 57-66, 2000.

Griggs, J.R. & Yeh, R.K. Labeling Graphs with a Condition at Distance Two, SIAM Journal of Discrete Mathematics, 5(4), pp.586-595, Nov 1992.

Georges, J.P., Mauro, D.W. & Stein, M.I., Labeling Products of Complete Graphs with a Condition at Distance Two, SIAM Journal of Discrete Mathematics, 14(1), pp. 28-35, 2001.

Georges, J.P. & Mauro, D.W., On Generalized Petersen Graphs Labeled with a Condition at Distance Two, Discrete Mathematics, 259, pp. 311-318, 2002.

Yeh, R.K., A Survey on Labeling Graphs with a Condition at Distance Two, Discrete Mathematics, 306, pp.1217-1231, 2006.

Bertossi, A. & Bonuccelli, M.A., Code Assignment for Hidden Terminal Interference Avoidance in Multihop Packet Radio Networks, IEEE/ACM Trans Networking, 3, pp.441-449, 1995.

Jin, X.T. & Yeh, R.K., Graph Distance-Dependent Labeling related to Code Assignment in Computer Networks, Wiley Interscience, 52, pp. 159-163, 2005.

Geetha K.N., Meera, K.N., Narahari, N. & Sooryanarayana, B., Open Neighborhood Coloring of Graphs, Int. J. Contemp. Math. Sciences, 8(14), pp.675-686, 2013.

Khan, N., Pal, M. & Pal, A., On L(0,1)- Labelling of Cactus Graphs, Communications and Network, 4, pp.18-29, 2012.