OJDM  Vol.2 No.3 , July 2012
Some New Results on Prime Graphs
Abstract: We investigate prime labeling for some graphs resulted by identifying any two vertices of some graphs. We also introduce the concept of strongly prime graph and prove that the graphs Cn, Pn, and K1,n are strongly prime graphs. Moreover we prove that Wn is a strongly prime graph for every even integer n ≥ 4.
Cite this paper: S. Vaidya and U. Prajapati, "Some New Results on Prime Graphs," Open Journal of Discrete Mathematics, Vol. 2 No. 3, 2012, pp. 99-104. doi: 10.4236/ojdm.2012.23019.

[1]   J. Gross and J. Yellen, “Graph Theory and Its Applications,’’ CRC Press, Boca Raton, 1999.

[2]   D. M. Burton, “Elementary Number Theory,” 2nd Edition, Brown Publishers, New York, 1990.

[3]   J. A. Gallian, “A Dynamic Survey of Graph Labeling,” The Electronic Journal of Combinatorics, Vol. 18, 2011.

[4]   A. Tout, A. N. Dabboucy and K. Howalla, “Prime Labeling of Graphs,” National Academy Science Letters, Vol. 11, 1982, pp. 365-368.

[5]   H. L. Fu and K. C. Huang, “On Prime Labellings,” Discrete Mathematics, Vol. 127, No. 1-3, 1994, pp. 181-186. doi:10.1016/0012-365X(92)00477-9

[6]   S. M. Lee, I. Wui and J. Yeh, “On the Amalgamation of Prime Graphs,” Bulletin of the Malaysian Mathematical Sciences Society (Second Series), Vol. 11, 1988, pp. 59-67.

[7]   T. Deretsky, S. M. Lee and J. Mitchem, “On Vertex Prime Labelings of Graphs,” In: J. Alvi, G. Chartrand, O. Oellerman, A. Schwenk, Eds., Graph Theory, Combinatorics and Applications: Proceedings of the 6th International Conference Theory and Applications of Graphs, Wiley, New York, 1991, pp. 359-369.

[8]   S. K. Vaidya and K. K. Kanani, “Prime Labeling for Some Cycle Related Graphs,” Journal of Mathematics Research, Vol. 2, No. 2, 2010, pp. 98-103. 4743

[9]   S. K. Vaidya and U. M. Prajapati, “Some Switching Invariant Prime Graphs,” Open Journal of Discrete Mathematics, Vol. 2, No. 1, 2012, pp. 17-20. doi:10.4236/ojdm.2012.21004

[10]   S. K. Vaidya and U. M. Prajapati, “Some Results on Prime and k-Prime Labeling,” Journal of Mathematics Research, Vol. 3, No. 1, 2011, pp. 66-75. 7881/6696

[11]   M. A. Seoud and M. Z. Youssef, “On Prime Labeling of Graphs,” Congressus Numerantium, Vol. 141, 1999, pp. 203-215.