d several results on prime cordial labeling. Vaidya and Vihol [6] have also discussed prime cordial labeling in the context of graph operations while in [7] the same authors have discussed prime cordial labeling for some cycle related graphs. Vaidya and Shah [8] have investigated many results on this concept. In the present paper we obtain some new prime cordial graphs.

Definition 1.6 Bistar is the graph obtained by joining the apex vertices of two copies of star.

Definition 1.7 For a graph G the split graph is obtained by adding to each vertex v a new vertex such that is adjacent to every vertex that is adjacent to v in G. The resultant graph is denoted as.

Definition 1.8 For a simple connected graph G the square of graph G is denoted by and defined as the graph with the same vertex set as of G and two vertices are adjacent in if they are at a distance 1 or 2 apart in G.

Definition 1.9 The middle graph M(G) of a graph G is the graph whose vertex set is and in which two vertices are adjacent if and only if either they are adjacent edges of G or one is a vertex of G and the other is an edge incident with it.

2. Main Results

Theorem 2.1 is a prime cordial graph.

Proof: Let be the pendant vertices, be the apex vertex of and are the vertices corresponding to in. Denoting then and .

To define, we consider following two cases.

Case 1: n = 2, 3 The graphs and are to be dealt separately and their prime cordial labeling is shown in Figure 1.

Case 2:

In view of the labeling pattern defined above we have (for n even) and

(for n odd). Thus we have

.

Hence is a prime cordial graph.

Illustration 2.2 Prime cordial labeling for is shown in Figure 2.

Figure 1., and their prime cordial labelling.

Figure 2. and its prime cordial labelling.

Theorem 2.3 is a prime cordial graph.

Proof: Consider with vertex set

where are pendant vertices. In order to obtain add vertices corresponding to where. If then and . We define vertex labeling as follows.

In view of pattern defined above we have .

That is,.

Hence is a prime cordial graph.

Illustration 2.4 Prime cordial labeling of the graph is shown in Figure 3.

Theorem 2.5 is a prime cordial graph.

Proof: Consider with vertex set where are pendant vertices. Let G be the graph then and .

To define, we consider following two cases.

Case 1:

The graphs and are to be dealt separately and their prime cordial labeling is shown in Figure 4.

Case 2:

Choose a prime number p such that,

, where is distinct even numbers between 4 and 2n + 2 except 2p with.

,

for.

In view of the above defined labeling pattern we have.

Thus in both the cases we have.

Hence is a prime cordial graph.

Illustration 2.6 Prime cordial labeling of the graph is shown in Figure 5.

Figure 3. and its prime cordial labelling.

Figure 4., and their prime cordial labelling.

Theorem 2.7 is not a prime cordial graph for = 2, 3.

Proof: Let and are respectively be the vertices and edges of. Add vertices corresponding to the edges in order to obtain middle graph of. Let be the graph. Then and.

For the graph the possible assignment of labels to adjacent vertices are (1,2), (1,3), (2,3). Such assignment will generate no edge with label 0 and two edges with label 1. That is,. Therefore is not a prime cordial graph.

For the graph the possible assignment of labels to adjacent vertices are (1,2),(1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (3,4), (3,5). Such assignment will generate maximum one edge with label 0 and minimum four edges with label 1. That is,. Therefore is not a prime cordial graph.

Hence is not a prime cordial graph for

Theorem 2.8 is a prime cordial graph for

Proof: Let and are respectively be the vertices and edges of. Add vertices corresponding to the edges in order to obtain middle graph of. Let be the graph. Then and . To define , we consider following two cases.

Case 1: is even,

In view of the above defined labeling pattern we have

.

Case 2: is odd,

Figure 5. and its prime cordial labelling.

,

,

In view of the above defined labeling pattern we have

Thus in both the cases we have.

Hence is a prime cordial graph for

Illustration 2.9 Prime cordial labeling of the graph is shown in Figure 6.

Theorem 2.10 is not a prime cordial graph for n = 3 to n = 7.

Proof: Let be the apex vertex of  wheel and be the rim vertices. Then and

For the graph the possible pairs of labels of adja-

Figure 6. and its prime cordial labelling.

cent vertices will be (1,2), (1,3), (1,4), (2,3), (2,4), (3,4). Such assignment will generate maximum one edge with label 0 and minimum five edges with label 1. That is,. Hence is not a prime cordial graph.

For the graph the possible assignment of labels to adjacent vertices will be (1,2), (1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (3,4), (3,5), (4,5). Such assignment will generate maximum one edge with label 0 and minimum seven edges with label 1. That is,. Hence is not a prime cordial graph.

For the graph the possible assignment of labels to adjacent vertices will be (1,2), (1,3), (1,4), (1,5), (1,6), (2,3), (2,4), (2,5), (2,6), (3,4), (3,5), (3,6), (4,5), (4,6), (5,6). Such assignment will generate maximum four edges with label 0 and minimum six edges with label 1. That is,. Hence is not a prime cordial graph.

For the graph the possible assignment of labels to adjacent vertices will be (1,2), (1,3), (1,4), (1,5), (1,6), (1,7), (2,3), (2,4), (2,5), (2,6), (2,7), (3,4), (3,5), (3,6), (3,7), (4,5), (4,6), (4,7), (5,6), (5,7), (6,7).  Such assignment will generate maximum four edges with label 0 and minimum eight edges with label 1. That is, . Hence is not a prime cordial graph.

Now in to satisfy the edge condition for prime cordial labeling it is essential to label seven edges with label 0 and seven edges with label 1 out of fourteen edges. But all the possible assignments of vertex labels will give rise to 0 labels for at most six edges and 1 labels for at least eight edges. That is,. Hence is not a prime cordial graph.

Hence Wn is not a prime cordial graph for n = 3 to n = 7.

Theorem 2.11 is a prime cordial graph for.

Proof: Let be the apex vertex of wheel and be the rim vertices. To define , we consider the following three cases.

Case 1: n = 8,9,10 The graphs, and are to be dealt separately and their prime cordial labeling is shown Figure 7.

Case 2: is even,

In view of the above defined labeling pattern we have

Case 3: is odd,

Figure 7., and and their prime cordial labelling.

In view of the above defined labeling pattern we have

Thus in all the cases we have.

Hence is a prime cordial graph for.

Illustration 2.12 Prime cordial labeling of the graph is shown in Figure 8.

3. Concluding Remarks

As not every graph admit prime cordial labeling it is very interesting to investigate graph or graph families which admit prime cordial labeling. In this paper we have investigated some new prime cordial graphs. To investigate similar results for other graph families as well as in the context of different labeling problems is an open area of research.

Figure 8. and its prime cordial labelling.

REFERENCES

  1. J. Gross and J. Yellen, “Graph Theory and Its Applications,” CRC Press, Boca Raton, 1999.
  2. L. W. Beineke and S. M. Hegde, “Strongly Multiplicative Graphs,” Discussiones Mathematicae Graph Theory, Vol. 21, 2001, pp. 63-75.
  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. I. Cahit, “Cordial Graphs: A Weaker Version of Graceful and Harmonious Graphs,” Ars Combinatoria, Vol. 23, 1987, pp. 201-207.
  5. M. Sundaram, R. Ponraj and S. Somasundram, “Prime Cordial Labeling of Graphs,” Journal of the Indian Academy of Mathematics, Vol. 27, No. 2, 2005 , pp. 373- 390.
  6. S. K. Vaidya and P. L. Vihol, “Prime Cordial Labeling for Some Graphs,” Modern Applied Science, Vol. 4, No. 8, 2010, pp. 119-126.
  7. S. K. Vaidya and P. L. Vihol, “Prime Cordial Labeling for Some Cycle Related Graphs,” International Journal of Open Problems in Computer Science and Mathematics, Vol. 3, No. 5, 2010, pp. 223-232.
  8. S. K. Vaidya and N. H. Shah, “Some New Families of Prime Cordial Graphs,” Journal of Mathematics Research, Vol. 3, No. 4, 2011, pp. 21-30. doi:10.5539/jmr.v3n4p21

Journal Menu >>