GRACEFUL CHROMATIC NUMBER OF SOME CARTESIAN PRODUCT GRAPHS

Abstract

A graph \(G(V,E)\) is a system consisting of a finite non empty set of vertices \(V(G)\) and a set of edges \(E(G)\). A (proper) vertex colouring of \(G\) is a function \(f:V(G)\rightarrow \{1,2,\ldots,k\},\) for some positive integer \(k\) such that \(f(u)\neq f(v)\) for every edge \(uv\in E(G)\). Moreover, if \(|f(u)-f(v)|\neq |f(v)-f(w)|\) for every adjacent edges \(uv,vw\in E(G)\), then the function \(f\) is called graceful colouring for \(G\). The minimum number \(k\) such that \(f\) is a graceful colouring for \(G\) is called the graceful chromatic number of \(G\). The purpose of this research is to determine graceful chromatic number of Cartesian product graphs \(C_m \times P_n\) for integers \(m\geq 3\) and \(n\geq 2\), and \(C_m \times C_n\) for integers \(m,n\geq 3\). Here, \(C_m\) and \(P_m\) are cycle and path with \(m\) vertices, respectively. We found some exact values and bounds for graceful chromatic number of these mentioned Cartesian product graphs.

Keywords

• graceful colouring, graceful chromatics number, cartesian product graph