Some Families of 3-Equitable Graphs

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 \( \bar{f}: E \to \{0,1,2\} \) defined by \( \bar{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 \( \bar{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)| \leq 1 \) and \( |e_f(i) – e_f(j)| \leq 1 \) for all \( i \neq 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 \geq 4 \)), (2) A Flower graph \( FL_n \), (3) One point union \( H_n^{(k)} \) of \( k \)-copies of \( H_n \), \( k \geq 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 \).