All submissions of the EM system will be redirected to Online Manuscript Submission System. Authors are requested to submit articles directly to Online Manuscript Submission System of respective journal.

Some Prime Labeling of Graph

B Kavitha1*, C Vimala2

1Department of Mathematics, Pondicherry University, Pondicherry, India

2Department of Mathematics, Vallam University, Tamil Nadu, India

*Corresponding Author:
B. Kavitha Department of Mathematics, Pondicherry University Pondicherry, India;Email:[email protected]

Received: 03-Mar-2022, Manuscript No. JSMS-22-55261; Editor assigned: 07-Mar-2022, Pre QC No. JSMS-22-52261(PQ); Reviewed: 21-Mar-2022, QC No. JSMS-22-55261; Revised: 02-May-2022, Manuscript No. JSMS-22-55261 (R); Published: 17-May-2022, DOI: 10.4172/JSMS.8.5.006.

Visit for more related articles at Research & Reviews: Journal of Statistics and Mathematical Sciences

Abstract

A graph G=(V(G), E(G)) with vertex set V is said to have a prime labeling if its vertices can be labeled with distinct positive integer 1,2,3 V such that for edge u v E(G), the labels assigned to u and v are relatively prime. A graph which admits prime labeling is called a prime graph. Graph labeling is an important area of research in Graph theory. There are many kinds of graph labeling such as graceful labeling, Magic labeling, Prime labeling, and other different labeling techniques. In this paper we discuss prime labeling for some graphs.

We also discuss prime labeling in the related of some graph operations namely cycle, path, crown, Fan, star and wheel graph.

Keywords

Labeling; Prime labeling; Prime labeling of path graph; Cycle graph; Crown graph; Fan graph; Star graph; Wheel graph

Introduction

In this article, we consider only finite simple undirected graph [1]. The graph G has vertex set V=V(G) and edge set E=E(G). The labeling of a graph G is an assigning of integers either to the vertices or edges or both subject to certain conditions. The notion of a prime labeling was introduced by Roger Entringer and was discussed in a paper [2] for notations and terminology, [3]. Many researchers have studied prime graph for example in Fu [4]. H has proved that the path Pn on n vertices is a prime graphhave proved that the Cn on n vertices is a prime graph [5]. We refer to have proved Edge Vertex Prime Labeling for Wheel, Fan and Friendship Graph [6]. have proved that wheel Wn is a prime graph [7]. have proved the prime labeling for some Fan related graphs [8]. For latest survey on graph labeling, we refer to [9] have proved the prime labeling for some cycle related graphs [10] have proved the Prime labeling for some fan related graphs. The following definitions and notations are used in main results [11].

Materials And Methods

  • Let G = (V(G), E(G)) be a graph with p vertices. A bijection f: V(G) → {1, 2, … p} is called a prime labeling if for each edge e = {u, v} belongs to E, we have gcd{f(u), f(v)} =1. A graph which admits prime labeling is called a prime graph.
  • A simple graph of ‘n’ vertices(n≥3) and n edges forming a cycle of length ‘n’ is called as a cycle graph. In a cycle graph, all the vertices are of degree is 2. By adding the path, the new vertices of v1, v2, … v m, and the new graph G is denoted by Cn @Pm
  • The crown graph on 2n vertices is an undirected graph with two set of vertices {u1, u2, … un} and {v1, v2, … v n} and with on edge from ui to vj whenever i ≠ j. By adding the path, the new vertices of w1, w2, … w m, and the new graph G is denoted by crown Cn @Pm
  • The Friendship graph F n is a graph which consists of ⴄ −triangles with a common vertex. If V(G) = 2n+1 and E(G) = 3n by adding the path, the new vertices of v1, v2, … v m, and the new graph G is denoted by F n @Pm
  • The star graph Sn is special type of graph in which n-1 vertices have degree 1 and single vertex have n-1 degree. This look like n-1 vertex is connected to central vertex. A star graph wit total n vertex is termed as Sn. By adding the path, the new vertices of v1, v2, … v m, and the new graph G is denoted by Sn @Pm
  • The wheel graph Wn is obtained by joining all vertices of a cycle Cn to a further vertex is called center. If V(G) = n+1 and E(G) = 2n by adding the path, the new vertices of v1, v2, … v m, and the new graph G is denoted by Wn @Pm
  • Gear graph Gn also known as a bipartite wheel graph is a wheel graph with a vertex added between each pair of adjacent vertices of the outer cycle. Gear graph Gn has 2r+1 vertices and 3r edges. By adding the path, the new vertices of w1, w2, … w m, and the new graph G is denoted by Gn @Pm

Results And Discussion

Theorem

The cycle and path graph are a prime graph. Then the graph Cn @ Pm prime labeling of the graph

Proof:

Let G be the graph obtained by joining cycle Cn and a path Pm, then the graph Cn @ Pm admit to prime labeling of the graph.

Let u1, u2, … un be the vertices of cycle Cn and v1, v2, … vn be the vertices of path Pm.

equation

Clearly vertex labels are distinct. Then f admits prime labeling. Thus, Cn @ Pm is a prime graph.

statistics-mathematical-prime

Figure 1: Prime labeling of graph Cn @ Pm

Prime labeling of graph C4 @ P6

The prime labeling of the graph is presented in the following graph.

statistics-mathematical-prime

Figure 2: Prime labeling of graph C4 @ P6

Theorem

The crown and path graph are a prime graph. Then the graph Cn @ Pm prime labeling of the graph

Proof:

Let G be the graph obtained by joining crown Cn by a path Pm admit to prime labeling of the graph.

Let u1, u2, … un be the vertices of crown Cn and v1, v2, … vn be the vertices of cycle Cn, then

w1, w2, … wn be the vertices of path Pm.

equation

Clearly vertex labels are distinct. Then f admits prime labeling. Thus, Cn @ Pm is a prime graph.

statistics-mathematical-prime

Figure 3: Prime labeling of crown graph Cn @ Pm

Prime labeling of graph crown C3 @ P4

The prime labeling of the graph is presented in the following graph.

statistics-mathematical-prime

Figure 4: Prime labeling of crown graph C3 @ P4

Theorem

The friendship and path graph are a prime graph. Then the graph Fn @ Pm prime labeling of the graph

Proof:

Let G be the graph obtained by joining friendship Fn by a path Pm admit to prime labeling of the graph.

Let u1, u2, … un be the vertices of friendship Fn and v1, v2, … vn be the vertices of path Pm.

equation

Clearly vertex labels are distinct. Then f admits prime labeling. Thus, Fn @ Pm is a prime graph.

statistics-mathematical-prime

Figure 5: Prime labeling of graph Fn @ Pm

Prime labeling of graph F3 @ P6

The prime labeling of the graph is presented in the following graph.

statistics-mathematical-prime

Figure 6: Prime labeling of graph F3 @ P6

Theorem

The star and path graph are a prime graph. Then the graph Sn @ Pm prime labeling of the graph

Proof:

Let G be the graph obtained by joining star Sn by a path Pm admit to prime labeling of the graph.

Let u0, u1, u2, … un be the vertices of star Sn and v1, v2, … vn be the vertices of path Pm.

equation

Clearly vertex labels are distinct. Then f admits prime labeling. Thus, Sn @ Pm is a prime graph.

statistics-mathematical-prime

Figure 7: Prime labeling of star graph Sn @ Pm

Prime labeling of graph S8 @ P5

The prime labeling of the graph is presented in the following graph.

statistics-mathematical-prime

Figure 8: Prime labeling of star graph S8 @ P5

Theorem

The wheel and path graph are a prime graph. Then the graph Wn @ Pm prime labeling of the graph

Proof:

Let G be the graph obtained by joining wheel Wn by a path Pm, admit to prime labeling of the graph.

Let u0, u1, u2… un be the vertices of wheel Wn and v1, v2…vn be the vertices of path Pm.

equation

Clearly vertex labels are distinct. Then f admits prime labeling. Thus, Wn @ Pm is a prime graph.

statistics-mathematical-prime

Figure 9: Prime labeling of graph Wn @ Pm

Prime labeling of graph W6 @ P5

The prime labeling of the graph is presented in the following graph

statistics-mathematical-prime

Figure 10: Prime labeling of wheel graph W6 @ P5

Theorem

The Gear and path graph are a prime graph. Then the graph Gn @ Pm prime labeling of the graph

Proof:

Let G be the graph obtained by joining Gear Gn by a path Pm.

Let u1, u2, …and v1, v2, …vn be the vertices of Gear Gn and w1, w2, … wn be the vertices path Pm.

equation

Clearly vertex labels are distinct.

Then f admits prime labeling. Thus, Gn @ Pm is a prime graph.

statistics-mathematical-prime

Figure 11: Prime labeling of graph Gn @ Pm

Prime labeling of graph G6 @ P5

The prime labeling of the graph is presented in the following graph.

statistics-mathematical-prime

Figure 12: Prime labeling of graph G5 @ P6

Conclusion

Prime labeling has been studied for then five decades. A huge number of research articles published in the area of graph theory and discrete mathematics. In this paper, we studied the prime labeling of some graph for, Cn@Pm, Fn@Pm, crown Cn@Pm, Sn@Pm and Wn@Pm, Gn@Pm in necessary conditions, In future work for some connected graphs.

References

Guvenilir Bahis Siteleri Guvenilir Bahis Siteleri Guvenilir Bahis Siteleri Guvenilir Casino Siteleri