Edge-gracefulness of the composition of paths with null graphs (Q1613519)

A graph \(G= (V,E)\) with vertex set \(V\) and edge set \(E\) is said to be a \((p,q)\)-graph if \(|V|= p\) and \(|E|= q\). Given two graphs \(G\) and \(H\), the composition of \(G\) and \(H\), denoted by \(G\circ H\), is the graph with vertex set \(V(G)\times V(H)\) in which \((u_1,v_1)\) is adjacent with \((u_2,v_2)\) if and only if \((u_1,u_2)\in E(G)\) or \(u_1= u_2\) and \((v_1,v_2)\in E(H)\). The paper studies the edge-gracefulness of the composition \(P_m\circ N_n\) of the path \(P_m\) and the null graph \(N_n\), where there are \(mn\) vertices and \((m-1)n^2\) edges. It is shown that \(P_3\circ N_n\) is edge-graceful if \(n\) is odd. This demonstrates that \(P_3\circ N_{6k+1}\), \(P_3\circ N_{6k+ 3}\), and \(P_3\circ N_{6k+5}\) are edge-graceful for \(k\geq 1\).