Some Families of 3-Equitable Graphs

Abstract

Let $G$ be a simple graph with vertex set $V$ and edge set $E$. A vertex labeling $f:V\to \{0,1,2\}$ induces an edge labeling $\overline{f}:E\to \{0,1,2\}$ defined by $\overline{f}(uv)=|f(u)–f(v)|$. Let $u_f(i)$ denote the number of vertices $v$ with $f(v)=i$, $i=0,1,2$. Similarly, $e_f(i)$ denotes the number of edges $uv$ with $\overline{f}(uv)=i$, $i=0,1,2$. A graph is said to be $3$-equitable if there exists a vertex labeling $f$ such that $|v_f(i)–v_f(j)|\le 1$ and $|e_f(i)–e_f(j)|\le 1$ for all $i\ne j$, $i,j=0,1,2$. In which case, $f$ is called a $3$-equitable labeling.

In this paper, we prove that the following graphs are three equitable: (1) Helm graph $H_n$ ($n\ge 4$), (2) A Flower graph $F{L}_n$, (3) One point union $H_n^{(k)}$ of $k$-copies of $H_n$, $k\ge 1$, (4) One point union $K_4^{(k)}$ of $k$ copies of $K_4$, (5) A $K_4$-snake of $n$ blocks, each equal to $K_4$, (6) A $C_t$-snake of $n$ blocks, $t=4,6$ and $t=5$ with $n$ not congruent to $3$ modulo $6$.