Open Journal of Discrete Mathematics
Vol.4 No.3(2014), Article ID:47452,7 pages DOI:10.4236/ojdm.2014.43009

Some Results on Prime Labeling*

U. M. Prajapati1, S. J. Gajjar2

1St. Xaviers College, Ahmedabad, India

2Government Polytechnic, Himmatnagar, India

Email: udayan64@yahoo.com, gjr.sachin@gmail.com

Copyright © 2014 by authors and Scientific Research Publishing Inc.

Received 7 May 2014; revised 5 June 2014; accepted 24 June 2014

ABSTRACT

In the present work we investigate some classes of graphs and disjoint union of some classes of graphs which admit prime labeling. We also investigate prime labeling of a graph obtained by identifying two vertices of two graphs. We also investigate prime labeling of a graph obtained by identifying two edges of two graphs. Prime labeling of a prism graph is also discussed. We show that a wheel graph of odd order is switching invariant. A necessary and sufficient condition for the complement of to be a prime graph is investigated.

Keywords:Graph Labeling, Prime Labeling, Switching of a Vertex, Switching Invariance

1. Introduction

We begin with simple, finite, undirected and non-trivial graph with the vertex set and the edge set. The number of elements of, denoted as is called the order of the graph while the number of elements of, denoted as is called the size of the graph. In the present work denotes the cycle with vertices and denotes the path of vertices. In the wheel the vertex corresponding to is called the apex vertex and the vertices corresponding to are called the rim vertices. For various graph theoretic notations and terminology we follow Gross and Yellen [1] whereas for number theory we follow D. M. 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 of the graph are assigned values subject to certain conditions then it is known as graph labeling.

For latest survey on graph labeling we refer to J. A. Gallian [3] . Vast amount of literature is available on different types of graph labeling and more than 1000 research papers have been published so far in last four decades. For any graph labeling problem following three features are really noteworthy:

Ÿ  a set of numbers from which vertex labels are chosen;

Ÿ  a rule that assigns a value to each edge;

Ÿ  a condition that these values must satisfy.

The present work is aimed to discuss one such labeling known as prime labeling.

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

The notion of prime labeling was originated by Entringer and was discussed in A.Tout [4] . Many researchers have studied prime graphs. It has been proved by H. L. Fu and C. K. Huang [5] that is a prime graph. It has been proved by S. M. Lee [6] that wheel graph is a prime graph if and only if is even. T. Deretsky [7] has proved that cycle is a prime graph.

Definition 1.3: A vertex switching of a graph is the graph obtained by taking a vertex of, removing all the edges incident to and adding edges joining to every other vertex which is not adjacent to in.

Definition 1.4: A prime graph is said to be switching invariant if for every vertex of, the graph obtained by switching the vertex in is also a prime graph.

Definition 1.5: For two graphs and their cartesian product is defined as the graph whose vertex set is and two vertices and in are adjacent if and is adjacent to or is adjacent to and.

Definition 1.6: is called prism graph.

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

2. Some Results on Prime Labeling

Theorem 2.1: If is a prime graph with order, where is even and is a graph with order 3 then disjoint union of and is a prime graph.

Proof: Let be the vertices of and be the vertices of. Let be a disjoint union of and. Now is a prime graph, so there is an injective function such that for any arbitrary edge, we have.

Define a function as follows:

Clearly is an injective function.

If is any edge of then. If then

. If then. If

then as is even.

Thus admits a prime labeling. So is a prime graph.

Theorem 2.2: If is a prime graph with order, where is divisible by 6 and is a prime graph with order 5 then disjoint union of and is a prime graph.

Proof: Let be the vertices of and be the vertices of. Let be the disjoint union of and. Now is a prime graph, so there exists an injective function

such that for any arbitrary edge of,. Also is a prime graph, so there is an injective function such that for any arbitrary edge of,. Define a function as follows:

Clearly is an injective function. To prove is a prime labeling of we have the following cases:

Case 1: If is any edge of then.

Case 2: Suppose is any edge of and. Here

is an odd natural number as is even and at least one of and is odd. As

and so. But possible values of are 1, 2, 3 and 4, and is odd. So or. If then and. Also, therefore and, which is not possible as. Thus, hence.

Thus admits prime labeling. So is a prime graph.

S. K. Vaidya and U. M. Prajapati [8] has proved that if is an even integer and is a natural number, then the graph obtained by identifying any of the rim vertices of a wheel with an end vertex of a path graph is a prime graph. But in the following theorem we have prove that if is odd then also it is prime.

Theorem 2.3: If, where is prime then the graph obtained by identifying one of the rim vertices of with an end vertex of is prime.

Proof: Let be an apex vertex of and be consecutive rim vertices of and are consecutive vertices of. Without loss of generality we can assume that be the graph obtained by identifying a rim vertex of with an end vertex of. Define as follows:

Clearly is an injective function. Let be an arbitrary edge of. To prove is a prime labeling of we have the following cases:

Case 1: If then,.

Case 2: If then,.

Case 3: If then,.

Case 4: If then.

Case 5: If then

Thus admits a prime labeling. So is a prime graph.

Theorem 2.4: A path and copies of cycle are given, then the graph obtained by identifying each edge of with an edge of a corresponding copy of the cycle is prime.

Proof: Let be the vertex of and be the vertices of copy of cycle where. Let be a graph obtained by identifying an edge of copy of cycle with an edge of path, where. Let be the set of vertices of then. Define a function as follows:

Clearly is an injective function. Let be an arbitrary edge of. To prove is a prime labeling of we have the following cases:

Case 1: If then, for.

Case 2: If then, for and.

Case 3: If then.

Case 4: If then.

Thus is a prime graph. So is a prime graph.

Theorem 2.5: A cycle and copies of a cycle are given, then the graph obtained by identifying each edge of with an edge of corresponding copy of the cycle is prime.

Proof: Let be the vertices of and be the vertices of copy of cycle where. Let be a graph obtained by identifying an edge of copy of cycle with an edge of cycle, where and an edge of copy of cycle with an edge of cycle . Let be the vertex set of then. Define a function as follows:

Clearly is an injective function. Let be an arbitrary edge of. To prove is a prime labeling of we have the following cases:

Case 1: If then, for.

Case 2: If then.

Case 3: If then, for and.

Case 4: If, , for.

Case 5: If then.

Case 6: If then, for .

Thus admits a prime labeling. So is a prime graph.

S. K. Vaidya and U. M. Prajapati [9] have proved that switching the apex vertex in is a prime graph and switching a rim vertex in is a prime graph if is prime. But in the following theorem we have proved that is switching invariant if is even.

Theorem 2.6: is switching invariant.

Proof: Let be rim vertices and be an apex vertex of. According to the degree of vertices of we can take the following cases.

Case 1: Let be a graph obtained by switching a rim vertex. Let be a largest prime less than.

Define a function as follows:

Clearly is an injective function. Let be an arbitrary edge of. To prove is a prime labeling of we have the following cases:

Ÿ If, then.

Ÿ If, then.

Ÿ If then.

Ÿ If, then .

Ÿ If, then, as is the largest prime less than.

Case 2: Let be a graph obtained by switching an apex vertex.

Define a function as follows:

Clearly is an injective function. It can be easily verified that is a prime labeling.

Thus from both the cases it follows that is a prime graph.

Theorem 2.7: The complement of is prime if and only if

Proof: We can easily see that is prime for and 6 from Figure 1.

Now if then and every rim vertex of is adjacent to other rim vertices. We have total even numbers to assign vertices. If one of the rim vertices is labeled as even number then other vertices can not be labeled as even number. Also remaining two rim vertices are adjacent, so only one of them can be labeled as even number. The apex vertex can also be labeled as even number. Thus maximum three vertices can be labeled as even number. But if then we have 4 or more even numbers to label. So it is not possible. Thus is not prime for.

Theorem 2.8: Let be a prime number and take copies of, then the graph obtained by identifying one vertex of each copy of with corresponding pendant vertex of is prime.

Proof: Let be an apex vertex and be pendant vertices of. Also let be the vertices of copy of. Now let be the graph obtained by identifying a pendant vertex of with a vertex of copy of, where.

Define a function, where as follows:

Clearly is an injective function. Let be an arbitrary edge of. To prove is a prime labeling of we have the following cases:

Case 1: If, , for.

Case 2: If, for and.

Case 3: If then for and,

Figure 1. Prime labeling of and.

Thus admits a prime labeling. So is a prime graph.

Theorem 2.9: If is an odd integer then the prism graph is not prime.

Proof: In the prism graph there are two cycles. So total number of vertices are. So we have to use 1 to natural numbers to label these vertices, and from 1 to there are even integers. If is odd then we can use at the most even integers to label the vertices of a cycle. We have such two cycles, so we can use at the most even integers to label the vertices of. But from 1 to there are even integers. So such prime labeling is not possible.

Thus is not prime if is an odd integer.

Theorem 2.10: If is a prime number then the prism graph is prime.

Proof: In the prism graph, let be the vertices of one cycle and,

be the vertices of the other cycle and a vertex is joined with by an edge for

. Define a function as follows:

Clearly is an injective function. Let be an arbitrary edge of. To prove is a prime labeling of we have the following cases:

Case 1: If then, for.

Case 2: If then, for.

Case 3: If then.

Case 4: If then.

Case 5: If then.

Case 6: If then, for.

Case 7: If then.

Thus admits a prime labeling. So is a prime graph.

Theorem 2.11: A graph obtained by joining every rim vertex of a wheel graph with corresponding vertex of a cycle is a prime graph, where is a prime number not less than 3.

Proof: Let be an apex vertex and be rim vertices of. Also are the vertices of. Let be the graph obtained by joining a vertex of with a vertex of by an edge, where. Define a function as follows:

Clearly is an injective function. Let be an arbitrary edge of. To prove is a prime labeling of we have the following cases:

Case 1: If then, for.

Case 2: If then.

Case 3: If then, for.

Case 4: If then, for.

Case 5: If then.

Case 6: If then, for.

Thus admits a prime labeling. So is a prime graph.

3. Concluding Remarks

Study of relatively prime numbers is very interesting in the theory of numbers and it is challenging to investigate prime labeling of some families of graphs. Here we investigate several results of some classes of graphs about prime labeling. Extending the study to other graph families is an open area of research.

Acknowledgements

The authors are highly thankful to the anonymous referee for valuable comments and constructive suggestions on the first draft of this paper.

References

1. Gross, J. and Yellen, J. (2004) Handbook of Graph Theory, CRC Press, Boca Raton.
2. Burton, D.M. (2007) Elementary Number Theory. 6th Edition, Tata McGraw-Hill Publishing Company Limited, New Delhi.
3. Gallian, J.A. (2012) A Dynamic Survey of Graph Labeling. The Electronic Journal of Combinatorics, 19, # DS6.
4. Tout, A., Dabboucy, A.N. and Howalla, K. (1982) Prime Labeling of Graphs. National Academy Science Letters, 11, 365-368.
5. Fu, H.L. and Huang, K.C. (1994) On Prime Labellings. Discrete Mathematics, 127, 181-186. http://dx.doi.org/10.1016/0012-365X(92)00477-9
6. Lee, S.M., Wui, I. and Yeh, J. (1988) On the Amalgamation of Prime Graphs. Bull. of Malaysian Math. Soc., 11, 59-67.
7. Deretsky, T., Lee, S.M. and Mitchem, J. (1991) On Vertex Prime Labelings of Graphs. In: Alvi, J., Chartrand, G., Oellerman, O. and Schwenk, A., Eds., Graph Theory, Combinatorics and Applications. Proceedings of the 6th International Conference Theory and Applications of Graphs, Wiley, New York, 359-369.
8. Vaidya, S.K. and Prajapati, U.M. (2011) Some Results on Prime and K-Prime Labeling. Journal of Mathematics Research, 3, 66-75. http://dx.doi.org/10.5539/jmr.v3n1p66
9. Vaidya, S.K. and Prajapati, U.M. (2012) Some Switching Invariant Prime Graphs. Open Journal of Discrete Mathematics, 2, 17-20. http://dx.doi.org/10.4236/ojdm.2012.21004

NOTES

*AMS subject classification number: 05C78.