Prime Labeling of Special Graph Classes Constructed from Dutch Windmill Graphs

Let G be a simple graph of order n. Prime labeling is a bijective function f: V (G) →1, 2, …, n such that gcd⁡ (f (u), f (v) ) =1 for every pair of adjacent vertices u, v in G. A graph G that satisfies the definition of prime labeling is called a prime graph. The Dutch windmill graph Dᵣⁿ is a graph obtained by taking n copies of cycle graph Cᵣ with a vertex in common. The double quadrilateral graph DQ is a graph constructed from two copies of C₄ and identifying one edge from each of them. The graph obtained by taking n copies of DQ and identifying one vertex of degree 3 from each of them as a common central vertex is called the double quadrilateral Dutch windmill graph DQₙ, for n≥1. Furthermore, graphs Dᵣⁿ and DQₙ becomes the base graph to construct two new graph classes, namely graph P₂ Dᵣⁿ and flower double quadrilateral graph FDQₙ. Both graph classes, constructed from the Dutch windmill graph, also contain even cycles. From previous research, it is known that graphs P₂ D₄ⁿ and flower double quadrilateral graph FDQₙ have odd harmonious labeling. However, the determination of prime labeling on both classes is still an open problem. In this paper, we show that two classes of graphs constructed from Dutch windmill graphs with even cycles, namely graphs P₂ D₄ⁿ and flower double quadrilateral graphs FDQₙ for n≥1 have a prime labeling. The result of this research shows that these graphs are prime graphs.