RUS  ENG
Full version
JOURNALS // Ural Mathematical Journal // Archive

Ural Math. J., 2023 Volume 9, Issue 2, Pages 193–208 (Mi umj215)

Graceful chromatic number of some cartesian product graphs

I. Nengah Supartaa, Mathiyazhagan Venkathacalamb, I Gede Aris Gunadia, Putu Andi Cipta Pratamaa

a Department of Mathematics, Universitas Pendidikan Ganesha, Jl. Udayana 11, Singaraja-Bali 81117, Indonesia
b Department of Mathematics, Kongunadu Arts and Science College, Coimbatore–641029, Tamil Nadu, India

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 chromatic number, cartesian product.

Language: English

DOI: 10.15826/umj.2023.2.016



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024