4-Cordiality of Some Regular Graphs and the Complete 4-Partite Graph

Abstract

Suppose $G$ is a graph with vertex set $V(G)$ and edge set $E(G)$, and let $A$ be an additive Abelian group. A vertex labeling $f:V(G)\to A$ induces an edge labeling $f^{\ast }:E(G)\to A$ defined by $f^{\ast }(xy)=f(x)+f(y)$. For $a\in A$, let $n_a(f)$ and $m_a(f)$ be the number of vertices $v$ and edges $e$ with $f(v)=a$ and $f^{\ast }(e)=a$, respectively. A graph $G$ is $A$-cordial if there exists a vertex labeling $f$ such that $|n_a(f)–n_b(f)|\le 1$ and $|m_a(f)–m_b(f)|\le 1$ for all $a,b\in A$. When $A={\mathbb{Z}}_k$, we say that $G$ is $k$-cordial instead of ${\mathbb{Z}}_k$-cordial. In this paper, we investigate certain regular graphs and ladder graphs that are $4$-cordial and we give a complete characterization of the $4$-cordiality of the complete $4$-partite graph. An open problem about which complete multipartite graphs are not $4$-cordial is given.