Cordial Labellings of the Cartesian Product and Composition of Graphs

Abstract

Let $G$ be a graph. A labelling $f:V(G)\to \{0,1\}$ is called a binary labelling of $G$. A binary labelling $f$ of $G$ induces an edge labelling $\lambda$ of $G$ as follows:
$$\lambda (u,v)=|f(u)–f(v)|$$ \quad for every edge $uv\in E(G)$.
Let $v_f(0)$ and $v_f(1)$ be the number of vertices of $G$ labelled with $0$ and $1$ under $f$, and $e_0(0)$ and $e_1(1)$ be the number of edges labelled with $0$ and $1$ under $\lambda$, respectively. Then the binary labelling $f$ of $G$ is said to be cordial if
$$|v_f(0)–v_f(1)|\le 1and|e_f(0)–e_f(1)|\le 1.$$

A graph $G$ is cordial if it admits a cordial labelling.

In this paper, we shall give a sufficient condition for the Cartesian product $G\times H$ of two graphs $G$ and $H$ to be cordial. The Cartesian product of two cordial graphs of even sizes is then shown to be cordial. We show that the Cartesian products $P_n\times P_n$ for all $n\ge 2$ and $P_n\times C_{4m}$ for all $m$ and all odd $n$ are cordial. The Cartesian product of two even trees of equal order such that one of them has a $2$-tail is shown to be cordial. We shall also prove that the composition $C_n[K_2]$ for $n\ge 4$ is cordial if and only if $n\ne 2(\mathrm{mod}4)$. The cordiality of compositions involving trees, unicyclic graphs, and some other graphs are also investigated.