On the cordial labeling of certain trigraphs

Abstract

Let G be a graph that has n vertices and m edges. Let f: V(G) → {1,2,..., k} be a function that assigns to each vertex v ∈ G a positive integer f(v) ∈ {1,2,..., k}. We assign to each edge uv ∈ E(G) a label which is the gcd(f(u), f(v)). The function f is called k-prime cordial labeling of G if |v_f(i) − v_f(j)| ≤ 1 for all i, j ∈ {1,2,..., k} and |e_f(0) − e_f(1)| ≤ 1, where v_f(i) denotes the number of vertices labeled with i, e_f(1) and e_f(0) denote the number of edges labeled with 1 and not labeled with 1, respectively. In this paper, we introduce the concept of trigraph of a graph G, T3(G), and we show that the trigraph of a path P_n, T₃(P_n), and the trigraph of a cycle C_n, T₃(C_n) are 4-prime cordial graphs.