Some New Results on Prime Graphs


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.

Share and Cite:

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.

Conflicts of Interest

The authors declare no conflicts of interest.


[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.

Copyright © 2021 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.