Some Switching Invariant Prime Graphs
S. K. Vaidya, U. M. Prajapati
.

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 Pn and K1,n admit prime labeling. Moreover we discuss prime labeling for the graph obtained by switching of vertex in wheel Wn.

Share and Cite:

Vaidya, S. and Prajapati, U. (2012) Some Switching Invariant Prime Graphs. Open Journal of Discrete Mathematics, 2, 17-20. doi: 10.4236/ojdm.2012.21004.

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.

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] I. Niven and H. S. Zuckerman, “An Introduction to the Theory of Numbers,” 3rd Edition, Wiley Eastern Limited, New York, 1972. [3] 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 [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 Science Society (Second Series), Vol. 11, 1988, pp. 59-67. [7] 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. [8] 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