Open Journal of Discrete Mathematics
Vol. 2 No. 1 (2012) , Article ID: 17155 , 4 pages DOI:10.4236/ojdm.2012.21004
Some Switching Invariant Prime Graphs
1Department of Mathematics, Saurashtra University, Rajkot, India
2St. Xavier’s College, Ahmedabad, India
Email: samirkvaidya@yahoo.co.in, udayan64@yahoo.com
Received November 12, 2011; revised December 10, 2011; accepted December 31, 2011
Keywords: Prime labeling; Switching of a vertex; Switching invariance
ABSTRACT
We investigate prime labeling for some graphs resulted from switching of a vertex. We discuss switching invariance of some prime graphs and prove that the graphs obtained by switching of a vertex in 
and 
admit prime labeling. Moreover we discuss prime labeling for the graph obtained by switching of vertex in wheel
.
1. Introduction and Definitions
We begin with simple, finite, undirected and non-trivial graph
, with vertex set 
and edge set
. Throughout this work 
denotes the cycle with 
vertices and 
denotes the path of 
vertices. In wheel 
the vertex corresponding to 
is called apex vertex and the vertices corresponding to 
are called rim vertices where
. The star 
is a graph with one vertex of degree 
called apex and 
vertices of degree one (pendant vertices). Throughout this paper 
and 
are the cardinality of vertex set and edge set respectively.
For various graph theoretic notations and terminology we follow Gross and Yellen [1] while for number theory we follow Niven and Zuckerman [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.
Vast amount of literature is available in printed as well as in electronic form on different types of graph labeling. More than 1300 research papers have been published so far in last four decades. 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: 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 are 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.
Vaidya and Kanani [8] have established the switching invariance of 
corresponding to prime labeling while in the present paper we investigate further results on prime graphs.
Bertarnad’s Postulate 1.5: For every positive integer 
there is a prime 
such that
.
2. Some Results on Prime Labeling with Respect to Vertex Switching Operation
Observation 2.1: Every prime graph 
of order 
has at least one vertex 
(corresponding to label 1) such that 
is a prime graph.
Observation 2.2: Let 
be a prime graph of order 
with a prime labeling. If 
is the vertex corresponding to the largest prime less then or equal to 
then 
is a prime graph.
Observation 2.3: Let 
be a prime graph of order 
with a prime labeling and 
is any arbitrary vertex having prime label from the set
then 
is a prime graph.
Theorem 2.4: 
is switching invariant.
Proof: Let 
be consecutive vertices of
. Let 
be the graph obtained by switching a vertex 
of
.
For the vertex 
we have the following possibilities:
1) 
then in
, 
is adjacent to 
.
Define 
as follows:
, where 
Then clearly 
is an injection.
For an arbitrary edge 
of 
we claim that
. Because a) if 
for some 
then 
;
b) if 
for some 
then 
as 
and 
are consecutive positive integers.
If 
the proof is similar as discussed above.
2) 
for some
. Then in
, 
is adjacent to all the vertices except 
and
.
Define 
as follows:
Then clearly 
is an injection.
For an arbitrary edge 
of 
we claim that
.
To prove our claim the following cases are to be considered.
a) If 
for some 
then 
;
b) If 
for some 
then 
.
c) If 
for some 
then 
as 
and 
are consecutive positive integers;
d) If 
for some 
then
;
Thus in each of the possibilities the graph 
under consideration admits a prime labeling. i.e. 
is a prime graph.
Thus 
and the graph obtained by switching of any vertex in 
are prime graphs. Hence the result.
Illustration 2.5: The prime labeling of the graph obtained by switching a pendant vertex of 
is shown in the Figure 1.
Illustration 2.6: The prime labeling of the graph obtained by switching a vertex of 
which is not a pendant vertex is shown in the Figure 2.
Theorem 2.7: 
is switching invariant.
Proof: We will separate two cases:
1) Switching of the apex vertex.
2) Switching of any pendant vertex.
Case 1: If 
is the apex vertex of 
and 
is the graph obtained by switching the apex vertex 
then 
is the null graph 
on 
vertices, which does not have any edge. Then obviously it is a prime graph.
Case 2: Let 
be the apex vertex and 
be the consecutive pendant vertices of
. Let 
be the graph obtained by switching the pendant vertex 
of
. So in 
every vertex 
other than 
and 
is adjacent to 
and 
only. By Bertrand’s postulate of number theory there exists at least one prime
such that 
then it is possible to define
as follows:
In view of the pattern defined above 
admits a prime labeling on
. Hence 
is a prime graph.
Thus 
and the graph obtained by switching any vertex of 
are prime graphs. Hence the result.
Illustration 2.8: The prime labeling of the graph obtained by switching a pendant vertex of 
is shown in the Figure 3.
Theorem 2.9: Switching the apex vertex in 
is a prime graph.
Proof: Let 
be consecutive rim vertices of 
and 
be the apex vertex of
. Let 
be the graph obtained by switching the vertex
. Thus 
Figure 1. The prime labeling of the graph obtained by switching a pendant vertex of
.
Figure 2. The prime labeling of the graph obtained by switching a vertex of 
which is not a pendant vertex.
Figure 3. The prime labeling of the graph obtained by switching a pendant vertex of
.
is the disjoint union of 
and
.
Define 
as follows:
Then clearly 
is an injection.
For an arbitrary edge 
of 
we claim that
.
1) If 
for some 
then 
as 
and 
are consecutive positive integers.
2) If 
then 
.
Thus in each of the possibilities the graph 
admits a prime labeling. i.e. 
is a prime graph.
Illustration 2.10: The prime labeling of the graph obtained by switching the apex vertex of 
is shown in the Figure 4.
Theorem 2.11: Switching of a rim vertex of 
is a prime graph if 
is a prime number.
Proof: Let 
be consecutive rim vertices of 
and 
be the apex vertex of
. Let 
be the graph obtained by switching the vertex
.
Define 
as follows:
, 
and
.
Then clearly 
is an injection.
For an arbitrary edge 
of 
we claim that
.
1) If 
for some 
then 
as 
and 
are consecutive positive integers.
2) If 
for some 
then
.
3) If 
for some 
then 
as 
is a positive integer less than the prime number
.
Thus in each of the possibilities the graph 
under consideration admits a prime labeling. i.e. 
is a prime graph.
Illustration 2.12: The prime labeling of the graph obtained by switching a rim vertex of 
is shown in the Figure 5.
Proposition 2.13: The graph obtained by switching of
Figure 4. The prime labeling of the graph obtained by switching the apex vertex of
.
Figure 5. The prime labeling of the graph obtained by switching a rim vertex of
.
a rim vertex in 
is not a prime graph.
Proof: Let 
be consecutive rim vertices of 
and 
be the apex vertex of
. Let 
be the graph obtained by switching the vertex
.
If possible let 
be a prime labeling. As 
is adjacent to four vertices 
and 
is adjacent to six vertices
, the labels of 
and 
can not be even. Moreover we have to distribute four even labels among six vertices. Therefore at least two adjacent vertices from 
will receive the even labels which contradicts the fact that 
is a prime labeling.
We noticed that it is not easy to discuss the prime labeling of a graph obtained by switching any rim vertex of 
when 
is a composite number. However we prove a following result and pose a conjecture.
Theorem 2.14: Switching of a rim vertex in 
is a not a prime graph if 
is an even integer greater than 9.
Proof: Let 
be consecutive rim vertices and 
be the apex vertex of
. Let 
be the graph obtained by switching the vertex
. If possible assume that there exists a prime labeling 
on
.
Observe that in 
the number of even integers is equal to the number of odd integers in
which is
.
If a vertex 
is adjacent to at least 
vertices then it cannot be labeled with even integer otherwise each of its 
neighbours should receive the labels with odd integers. Consequently there should be at least 
odd integers in 
and at the most 
even integers. However, there are at least 5 even integers in
, a contradiction.
Consequently each of the vertices 
and 
have at least 
neighbours must be labeled with an odd integer. Therefore the remaining vertices 
forms a path 
in 
and these vertices will receive
odd labels and 
even labels. If
and 
denote the number of vertices with even labels and number of vertices with odd labels respectively in 
then
. Hence there must be two adjacent vertices in 
which will receive even labels which contradicts our assumption that 
is a prime labeling of
.
Conjecture 2.15: The graph obtained by switching of a rim vertex in 
is a not a prime graph if 
is a composite odd integer greater than 9.
3. Concluding Remarks
The study of prime numbers is 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 labeling of graphs and pose a conjecture. This discussion becomes more relevant as it is carried out in the context of a graph operation namely switching of a vertex. We have studied switching invariant behaviour of some standard graphs.
REFERENCES
- J. Gross and J. Yellen, “Graph Theory and Its Applications,” CRC Press, Boca Raton, 1999.
- I. Niven and H. S. Zuckerman, “An Introduction to the Theory of Numbers,” 3rd Edition, Wiley Eastern Limited, New York, 1972.
- J. A. Gallian, “A Dynamic Survey of Graph Labeling,” The Electronic Journal of Combinatorics, Vol. 17, 2010, #DS6. http:\\www.combinatorics.org\Surveys\ds6.pdf
- A. Tout, A. N. Dabboucy and K. Howalla, “Prime Labeling of Graphs,” National Academy Science Letters, Vol. 11, 1982, pp. 365-368.
- 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
- S. M. Lee, I. Wui and J. Yeh, “On the Amalgamation of Prime Graphs,” Bulletin of the Malaysian Mathematical Science Society (Second Series), Vol. 11, 1988, pp. 59-67.
- T. Deretsky, S. M. Lee and J. Mitchem, “On Vertex Prime Labelings of Graphs,” Proceedings of the 6th International Conference Theory and Applications of Graphs, Wiley, New York, 1991, pp. 359-369.
- S. K. Vaidya and K. K. Kanani, “Prime Labeling for Some Cycle Related Graphs,” Journal of Mathematics Rsearch, Vol. 2, No. 2, 2010, pp. 98-103. http:\\ccsenet.org\journal\index.php\jmr\article\view\4423\4743