Graceful chromatic number of some cartesian product graphs

I. Nengah Suparta ; Mathiyazhagan Venkathacalam ; I Gede Aris Gunadi ; Putu Andi Cipta Pratama

Ural mathematical journal, Tome 9 (2023) no. 2, pp. 193-208

Résumé

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.

Détail

Keywords: Graceful colouring, graceful chromatic number, cartesian product.