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.
This work is licensed under the Creative Commons Attribution International License (CC BY).
http://creativecommons.org/licenses/by/4.0/
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
- Gross, J. and Yellen, J. (2004) Handbook of Graph Theory, CRC Press, Boca Raton.
- Burton, D.M. (2007) Elementary Number Theory. 6th Edition, Tata McGraw-Hill Publishing Company Limited, New Delhi.
- Gallian, J.A. (2012) A Dynamic Survey of Graph Labeling. The Electronic Journal of Combinatorics, 19, # DS6.
- Tout, A., Dabboucy, A.N. and Howalla, K. (1982) Prime Labeling of Graphs. National Academy Science Letters, 11, 365-368.
- 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
- Lee, S.M., Wui, I. and Yeh, J. (1988) On the Amalgamation of Prime Graphs. Bull. of Malaysian Math. Soc., 11, 59-67.
- 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.
- 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
- 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.