Open Journal of Discrete Mathematics
Vol.2 No.3(2012), Article ID:21145,6 pages DOI:10.4236/ojdm.2012.23019

Some New Results on Prime Graphs

Samir K. Vaidya1, Udayan M. Prajapati2

1Saurashtra University, Rajkot, India

2St. Xavier’s College, Ahmedabad, India

Email: samirkvaidya@yahoo.co.in, udayan64@yahoo.com

Received May 6, 2012; revised June 13, 2012; accepted June 25, 2012

Keywords: Prime Labeling; Prime Graph; Strongly Prime Graph

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.

1. Introduction

We begin with finite, undirected and non-trivial graph with the vertex set and the edge set. Throughout this work denotes the cycle with vertices and denotes the path on vertices. In the wheel the vertex corresponding to is called the apex vertex and the vertices corresponding to are called the rim vertices, where. The star is a graph with one vertex of degree called apex and vertices of degree one called pendant vertices. Throughout this paper and denote the cardinality of vertex set and edge set respectively.

For various graph theoretic notation and terminology we follow Gross and Yellen [1] while for number theory we follow Burton [2]. We will give brief summary of definitions and other information which are useful for the present investigations.

Definition 1.1: If the vertices are assigned values subject to certain condition(s) then it is known as graph labeling.

Vast amount of literature is available in printed as well as in electronic form on different kind of graph labeling problems. For a dynamic survey of graph labeling problems along with extensive bibliography we refer to Gallian [3].

Definition 1.2: A prime labeling of a graph is an injective function such that for every pair of adjacent vertices and,. The graph which admits a prime labeling is called a prime graph.

The notion of a prime labeling was originated by Entringer and was discussed in a paper by Tout et al. [4]. Many researchers have studied prime graphs. For e.g. Fu and Huang [5] have proved that and are prime graphs. Lee et al. [6] have proved that is a prime graph if and only if is even. Deretsky et al. [7] have proved that is a prime graph.

Definition 1.3: Let u and v be two distinct vertices of a graph. A new graph is constructed by identifying (fusing) two vertices u and v by a single new vertex x such that every edge which was incident with either u or v in is now incident with x in.

Vaidya and Kanani [8] have established that the graph obtained by identifying any two vertices and (with) of () is a prime graph. The switching invariance of various prime graphs is discussed by Vaidya and Prajapati [9]. In the present paper we investigate further results on prime graphs.

Bertrand’s Postulate 1.4: For every positive integer there is a prime such that.

2. Prime Labeling of Some Graphs

Theorem 2.1: The graph obtained by identifying any two vertices of is a prime graph.

Proof: The result is obvious for. Therefore we start with. Let be the apex vertex and be the consecutive pendant vertices of. Due to the nature of two vertices can be identified in following two possible ways:

Case 1: The apex vertex is identified with any of the pendant vertices (say). Let the new vertex be and the resultant graph be.

Then, for and as there is a loop incident at. Define as for and. Obviously f is an injection andfor every pair of adjacent verticesand of. Hence is a prime graph.

Case 2: Any two of the pendant vertices (say and) are identified. Let the new vertex be and the resultant graph be G. So in G, , for , and. Define as for and. Obviously f is an injection and for every pair of adjacent vertices and of. Hence is a prime graph.

Illustration 2.2: The prime labeling of the graph obtained by identifying the apex vertex with a pendant vertex of is shown in Figure 1.

Illustration 2.3: The prime labeling of the graph obtained by identifying two of the pendant vertices of is shown in Figure 2.

Theorem 2.4: If is a prime and is a prime graph of order then the graph obtained by identifying two vertices with label 1 and is also a prime graph.

Proof: Let f be a prime labeling of and be the label of the vertex for. Moreover be the new vertex of the graph which is obtained by identifying and of. Define as

Then

Obviously is an injection. For an arbitrary edge of we claim that. To prove our claim the following cases are to be considered.

Case 1: If then = = = 1.

Case 2: If and then ==.

Case 3: If and then for some with then = = as and are adjacent vertices in the prime graph with the prime labelling. Thus in all the possibilities admits a prime labeling for. Hence is a prime graph.

Illustration 2.5: In the following Figures 3 and 4 prime labeling of a graph of order 5 and the prime labeling for the graph obtained by identifying the vertices of with label 1 and 5 are shown.

Theorem 2.6: The graph obtained by identifying any two vertices of is a prime graph.

Proof: Let be the vertices of. Let be the new vertex of the graph obtained by identifying two distinct vertices and of. Then is nothing but a cycle (possibly loop) with at the most two

Figure 1. The prime labeling of the graph obtained by identifying the apex vertex with a pendant vertex in K1,7.

Figure 2. The prime labeling of the graph obtained by identifying two of the pendant vertices in K1,7.

Figure 3. The prime labeling of a graph of order five.

Figure 4. The prime labeling of the graph obtained by identifying the vertices of Figure 3 with label 1 and 5.

paths attached at. Such graph is a prime graph as proved in Vaidya and Prajapati [10].

Illustration 2.7: In the following Figures 5-9 prime labelings for and the graphs obtained by identifying two vertices in various possible ways are shown.

3. Strongly Prime Graphs

Definition 3.1: A graph G is said to be a strongly prime

Figure 5. A prime labeling of P5.

Figure 6. A prime labeling of the graph obtained by identifying v1 and v2 of P5 of Figure 5.

Figure 7. A prime labeling of the graph obtained by identifying v1 and v3 of P5 of Figure 5.

Figure 8. A prime labeling of the graph obtained by identifying v1 and v4 of P5 of Figure 5.

Figure 9. A prime labeling of the graph obtained by identifying v1 and v5 of P5 of Figure 5.

graph if for any vertex of there exits a prime labeling f satisfying.

Observation 3.2: is a strongly prime graph as any vertex of can be assigned label 1 and the remaining vertices can be assigned label 2 and 3 as shown in Figure 10.

Observation 3.3: If is an edge of then is a prime graph (see Figure 11) but it is not a strongly prime graph. If possible either of the vertices of with degree 2 can be assigned the label 1. Suppose is assigned the label 1 then available vertex labels for the remaining three vertices of are 2, 3 and 4. Consequently the vertices corresponding to the labels 2 and 4 are adjacent in. See Figure 12.

Observation 3.4: Every spanning subgraph of a strongly prime graph is a strongly prime graph. Because every spanning subgraph of a prime graph is a prime graph as proved by Seoud and Youssef [11].

Theorem 3.5: Every path is a strongly prime graph.

Proof: Let be the consecutive vertices of. If is any arbitrary vertex of then we have the following possibilities:

Case 1: If is either of the pendant vertices (say) then the function defined by, for all, is a prime labeling for with.

Case 2: If is not a pendant vertex then for some then the function defined by

is a prime labeling with.

Thus from the cases described above is a strongly prime graph.

Illustration 3.6: It is possible to assign label 1 to arbitrary vertex of in order to obtain different prime labeling as shown in Figures 13-18.

Theorem 3.7: Every cycle is a strongly prime graph.

Proof: Let be the consecutive vertices of. Let be an arbitrary vertex of. Then for some. The function defined by

is a prime labeling for with. Thus admits prime labeling as well as it is possible to assign label 1 to any arbitrary vertex of. That is, is strongly prime graph.

Theorem 3.8: is a strongly prime graph.

Proof: For, 2 the respective graphs and are strongly prime graphs as proved in the Theorem 3.5.

Figure 10. A strongly prime labeling of.

Figure 11. A prime labeling of.

Figure 12. is not a strongly prime graph.

Figure 13. A prime labeling of having as label 1.

Figure 14. A prime labeling of having as label 1.

Figure 15. A prime labeling of having as label 1.

Figure 16. A prime labeling of P5 having v4 as label 1.

Figure 17. A prime labeling of having as label 1.

Figure 18. A prime labeling of having as label 1.

For let be the apex vertex and be the pendant vertices of.

If is any arbitrary vertex of then we have the following possibilities:

Case 1: If is the apex vertex then. Then the function defined by for is a prime labeling on with.

Case 2: If is one of the pendant vertices then for some. Define, , where is the largest prime less than or equal to and the remaining vertices are distinctly labeled from. According to Bertrand’s postulate. Therefore is co-prime to every integer from. Thus every edge is incident to the apex vertex whose label is, thus or. Hence this function admits a prime labeling on with.

Thus from all the cases described above is a strongly prime graph.

Illustration 3.9: It is possible to assign label 1 to arbitrary vertex of in order to obtain prime labeling as shown in Figures 19 and 20.

Theorem 3.10: is a strongly prime graph for every even positive integer.

Proof: Let be the apex vertex and be the consecutive rim vertices of. Let be an arbitrary vertex of. We have the following possibilities:

Case 1: is the apex vertex of that is. Then the function defined as

. (1)

Obviously is an injection. For an arbitrary edge of we claim that. To prove our claim the following subcases are to be considered.

Subcase (1): if e = vivi+1 for some

Figure 19. A prime labeling of K1,7 with the apex vertex as label 1.

Figure 20. A prime labeling of K1,7 with a pendant vertex as label 1.

then = = as and are consecutive positive integers.

Subcase (2): if then = as is an odd integer and it is not divisible by 2.

Subcase (3): if for some then =.

Case 2: is one of the rim vertices. We may assume that where is the largest prime less than or equal to. According to the Bertrand’s Postulate such a prime exists with. Define a function as

(2)

The only difference between the definition of labeling functions of (1) and (2) is the labels 1 and are interchanged. Then clearly is an injection.

For an arbitrary edge of we claim that. To prove our claim the following subcases are to be considered.

Subcase (2): If for some then as is co-prime to every integer from.

Subcase (2): If for some then as and are consecutive positive integers.

Subcase (3): If for then =.

Subcase (4): If for then

Thus in all the possibilities described above admits prime labeling as well as it is possible to assign label 1 to any arbitrary vertex of. That is, is a strongly prime graph for every even positive integer.

Illustration 3.11: It is possible to assign label 1 to arbitrary vertex of in order to obtain prime labeling as shown in Figures 21 and 22.

Corollary 3.12: The friendship graph is a strongly prime graph.

Figure 21. A prime labeling of W8 with the apex vertex as label 1.

Figure 22. A prime labeling of W8 with a rim vertex as label 1.

Proof: The friendship graph is a one point union of copies of. It can also be thought as a graph obtained by deleting every alternate rim edge of. Being a spanning subgraph of strongly prime graph, is a strongly prime graph.

Corollary 3.13: The star is a strongly prime graph.

Proof: is obtained from strongly prime graph by deleting all the rim edges of the. Being a spanning subgraph of strongly prime graph, is a strongly prime graph.

4. Concluding Remarks

The prime numbers and their behaviour are of great importance as prime numbers are scattered and there are arbitrarily large gaps in the sequence of prime numbers. If these characteristics are studied in the frame work of graph theory then it is more challenging and exciting as well.

Here we investigate several results on prime graphs. This discussion becomes more interesting in the situation when two vertices of a graph are identified. We also introduce a concept of strongly prime graph. As every prime graph is not a strongly prime graph it is very exciting to investigate graph families which are strongly prime graphs. We investigate several classes of prime graph which are strongly prime graph.

5. Acknowledgements

The authors are highly thankful to the anonymous referee for valuable comments and constructive suggestions.

REFERENCES

  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. http://www.combinatorics.org/Surveys/ds6.pdf
  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. http://ccsenet.org/journal/index.php/jmr/article/view/4423/ 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. http://ccsenet.org/journal/index.php/jmr/article/download/ 7881/6696
  11. M. A. Seoud and M. Z. Youssef, “On Prime Labeling of Graphs,” Congressus Numerantium, Vol. 141, 1999, pp. 203-215.