On prime labelings of the second power of paths with other graphs

Abstract

A graph G with vertex set V(G) and edge set E(G) is said to have a prime labeling if its vertices can be labeled with distinct integers 1, 2, 3, ⋯, |V| such that for each xy ∈ E(G) the labels assigned to x and y are relatively prime. The second of paths P²_n, is the graph obtained from the path P_n by adding edges that join all vertices u and v with d(u, v)= 2. In this paper, we prove that certain combinations of second power of paths, paths and cycles are prime. Specifically, we investigate the prime labeling of the join and the union of pairs of second power of paths and graphs consisting of one second power of path and one path and one cycle.