Complete Partite Graphs

We use the following observation in $Lemma$ 2.6 and $Lemma$ 2.7.

Observation 2.1   Let ${\cal Z} \in \hbox{Z\kern-.35em\hbox{Z}}^+$ and let $0<a_i<\cal Z$ for $1 \le i \le n$ be integers. Let $d=gcd(a_1,a_2,...,a_n)$. Then there exist nonnegative integers $L_i$ for $1 \le i \le n$ such that $\sum^{n}_{i=1} L_i a_i \equiv d$.

Discussion. Since $d=gcd(a_1,a_2,...,a_n)$, there exist $K_i \in \hbox{Z\kern-.35em\hbox{Z}}$ such that $d=\sum^{n}_{i=1} K_i a_i$. Let $f: \hbox{Z\kern-.35em\hbox{Z}}\rightarrow \{0,1,...,{\cal{Z}}-1\}$ by $f(x)= x$ $(mod$ $\cal Z)$. Then $0 \le f(x)< \cal Z$, $f(xy) \equiv f(x)f(y)$, and $f(x+y) \equiv f(x)+f(y)$. Since $0<a_i<\cal Z$, for $1 \le i \le n$, then $f(a_i) =a_i$. Also $0< d < a_i$ for all $a_i$. So $f(d)=d$. Therefore $d=f(d) \equiv f( \sum^{n}_{i=1} K_i a_i) \equiv \sum^{n}_{i=1} f(K_i)f(a_i) \equiv \sum^{n}_{i=1} f(K_i) a_i$, where $f(K_i)$ are nonnegative integers for $1 \le i \le n$. $\Box$

The following lemma is needed for $Corollary$ 2.3.

Lemma 2.2   For $\hbox{I\kern-.25em\hbox{K}}_{n_1,n_2,...,n_m}$, with $a_1,a_2 \in V_1, b \in V-V_1$, and $\vert V_1 \vert \ge 3$, if $a_1+b \in V-V_1$, then $a_2+b \not \equiv a_1$.

Proof. If $a_2=a_1$, then $a_2+b=a_1+b \in V-V_1$, and the result follows. Suppose for the sake of contradiction, $a_2+b \equiv a_1$. Since $\vert V_1 \vert \ge 3$, there exist $a_3 \in V_1$ such that $a_3 \notin \{a_1,a_2 \}$. Now $\{a_3, b+a_1\} \in E,$ since $a_3 \in V_1$ and $b+a_1 \in V-V_1$. Thus $a_3+b+a_1 \in \cal F$. Notice $a_3+b \in \cal F$ and $a_3+b \not \equiv a_2+b \equiv a_1$. So $\{a_3+b,a_1\} \in E$ which implies $a_3+b \in V-V_1$. Hence $\{a_3+b,a_2\} \in E$ and so $a_3+b+a_2 \in \cal F$. By assumption $a_3 \not \equiv a_1 \equiv b+a_2,$ therefore $\{a_3,b+a_2\} \in E,$ a contradiction. $\Box$

The following corollary is cited in $Lemma$ 2.4, $Lemma$ 2.5, and $Lemma$ 2.6.

Corollary 2.3   Let $V_1$ be a partite set of $\hbox{I\kern-.25em\hbox{K}}_{n_1,n_2,...,n_m}$ with $\vert V_1 \vert \ge 3$. If $a_1 \in V_1$, $b \in V-V_1$, then either for all $a_i \in V$, $a_i+b \notin V-V_1$, or for all $a_i \in V$, $a_i+b \in V-V_1$

Proof. If for all $a_i \in V_1$, $a_i+b \notin V-V_1$, the result follows. Assume there exist a $a_i \in V$ such that $a_i+b \in V-V_1$. Pick $a_j \in V_1$. Then $\{a_j,a_i+b\} \in E$ since $a_j \in V_1$ and $a_i+b \in V-V_1$. So $a_j+a_i+b \in \cal F$. Also $a_j+b \in \cal F$, since $a_j \in V$ and $b \in V-V_1$. By $Lemma$ 2.2, $a_j+b \not \equiv a_i$. So $\{a_i,a_j+b\} \in E$. This implies $a_j+b \in V-V_1$. $\Box$

The next lemma is used in $Lemma$ 2.5.

Lemma 2.4   Let $V_1$ and $V_2$ be partite sets of $\hbox{I\kern-.25em\hbox{K}}_{n_1,n_2,...,n_m}$, with $\vert V_1 \vert = n_1, \vert V_2 \vert =n_2$ and $n_2, n_1 \ge 3$. Suppose $a \in V_1$, $b \in V_2$. If $a+b \in V_1$, then for all $b \in V_2$, $a+b \in V_1$.

Proof. Denote $V_1 =\{ a_1,a_2,...,a_{n_1} \}$, $V_2 =\{b_1,b_2,...,b_{n_2} \}$, and suppose $a_1 +b_1 \in V_1$. By $Corollary$ 2.3, since $a_1 +b_1 \in V-V_2$, then for every $b_i \in V_2$, $a_1 +b_i \in V-V_2$. Likewise since $a_1 +b_1 \notin V-V_1$, for every $a_j \in V_1$, $a_j+b_1 \notin V-V_1$. If for every $b_i$, $a_1 +b_i \in V_1$, the result follows. Suppose there exist a $b_2$ such that $a_1+b_2 \notin V_1$. Now $b_2+a_1 \in V-V_2$. So $b_2+a_1 \in V-V_2-V_1 \subset V-V_1$. Thus $b_2+a_i \in V-V_1$, for all $a_i \in V_1$ by $Corollary$ 2.3. Pick $a_i \in V_1$. Since $b_1+a_1 \in V_1$ and $b_2+a_i \in V-V_1$, then $\{b_1+a_1,b_2+a_i\} \in E$. Hence $b_1+a_1+b_2+a_i \in \cal F$. Now we showed $b_1+a_i \notin V-V_1$, then $b_1+a_i \in V_1$ or $b_1+a_i \in R$. Well $b_2+a_1 \in V-V_1$, so $b_1+a_i \not \equiv b_2+a_1$. Hence $\{b_1+a_i,b_2+a_1\} \in E$ which implies $b_1+a_i \in V_1$. Therefore $b_1+a_i \in V_1$ for all $a_i \in V_1$. So $a_1,b_1+a_1,b_1+b_1 +a_1,...,nb_1+a_1,... \in V_1$. Hence there exist a smallest $J \in Z^+$ such that $b_1(J+1) \equiv 0$ and $kb_1+a_1 \in V_1$ for $0\le k \le J$. Since $b_2+a_i \in V-V_1$ for all $a_i \in V_1$, then $b_2+kb_1+a_1 \in V-V_1$ for $0\le k \le J$. Then $\{b_2+kb_1+a_1,a_1\} \in E$ which implies $b_2+kb_1+2a_1 \in F$ for $0\le k \le J$. Hence for $0 \le k < J$, $b_2+kb_1+2a_1 \not \equiv 0$, so $b_2+(k+1)b_1+2a_1 \not \equiv b_1$ for $1 \le k \le J$. Also $b_2+2a_1 \not \equiv b_1$, since $b_2+Jb_1+2a_1 \not \equiv 0$. Notice $b_2+kb_1+2a_1 +b_1 \in \cal F$ for $0\le k \le J$. So $\{b_2+kb_1+2a_1,b_1\} \in E$ implies $\{b_2+kb_1+2a_1,b_2\} \in E$ implies $2b_2+kb_1+2a_1 \in \cal F$ for $0\le k \le J$. Suppose for $l>0$, $lb_2+kb_1+2a_1 \in \cal F$ for $0\le k \le J$. So by the previous argument for $0\le k \le J$, $lb_2+kb_1+2a_1 \not \equiv b_1$ and $lb_2+(k+1)b_1+2a_1 \in \cal F$. Hence $\{lb_2+kb_1+2a_1,b_1\} \in E$ implies $\{lb_2+kb_1+2a_1,b_2\} \in E$ implies $(l+1)b_2+kb_1+2a_1 \in \cal F$ for $0\le k \le J$. Whence $lb_2+b_1+2a_1 \in \cal F$ for all $l \ge 0$. So there must exist $K>N$ such that $Kb_2+b_1+2a_1 \equiv Nb_2+b_1+2a_1$. So $(K-N)b_2 \equiv 0$. Therefore $(K-N)b_2+b_1+2a_1 \equiv b_1+2a_1 \in \cal F$. Now $b_1+a_1 \not \equiv a_1$ since $b_1 \not \equiv 0$. So $\{b_1+a_1,a_1\} \in E$, a contradiction. $\Box$

The following result is an extension to a result by Hartfield and Smyth in [#!hs1!#], the lemma is referenced in $Lemma$ 2.6, $Theorem$ 2.10, and $Theorem$ 2.11.

Lemma 2.5   Let $V_1$ and $V_2$ be partite sets of $\hbox{I\kern-.25em\hbox{K}}_{n_1,n_2,...,n_m}$, with $\vert V_1 \vert = n_1, \vert V_2 \vert =n_2$ and $n_2 \ge n_1 \ge 3$. Suppose $b_1 \in V_2$. Then either for all $a_i \in V_1$, $a_i+b_1 \in R$, or for all $a_i \in V_1, a_i+b_1 \in V-V_1$.

Proof. Suppose $a_1 \in V_1$, $b_1 \in V_2$, and $a_1 +b_1 \in V-V_1$. So by $Corollary$ 2.3 for all $a_i \in V_1, a_i+b_1 \in V-V_1$. Now suppose $a_1 +b_1 \in V_1$. By $Lemma$ 2.4 for every $b_i \in V_2$, $a_1 +b_i \in V_1$. So $a_1, a_1+b_i \in V_1$ for $1 \le i \le n_2$, but $a_1 \not \equiv a_1 +b_i$. Also $a_1+b_i \not \equiv a_1+b_j$ for $i \ne j$. Thus $a_1, a_1+b_i$ for $1 \le i \le n_2$ are $n_2+1$ distinct elements in $V_1$, a contradiction since $n_2 \ge \vert V_1 \vert$. Finally, observe that if $a_1+b_1 \in R$, then by the conclusion of the previous paragraph, there exists no vertex $a_i \in V_1$ such that $a_i+b_1 \in V$. This completes the proof. $\Box$

The next lemma is needed in $Lemma$ 2.7.

Lemma 2.6   Suppose $K_{n_1,n_2,...,n_m}$ is a MSG, i.e. $V =\cal F$, with $V_1$ and $V_2$ partite sets and $\vert V_2 \vert = n_2 \ge \vert V_1 \vert = n_1 \ge 3$. If $V_1 =\{ a_1,a_2,...,a_{n_1} \}$ with $gcd(a_1,a_2,...,a_{n_1})=d$, then there exist $L \in \hbox{Z\kern-.35em\hbox{Z}}^+$ such that $(L+1)d \equiv Z$ and for all $b \in V_2$, $i\in \hbox{Z\kern-.35em\hbox{Z}}$, $b+id \in V-V_1$.

Proof. Denote $V_2 =\{b_1,b_2,...,b_{n_2} \}$. By assumption $\vert R \vert =0$, so by $Lemma$ 2.5, $b_i+a_j \in V-V_1$ for $1 \le i \le n_2, 1\le j \le n_2$. Pick $b \in V_2$. Assume there exist nonnegative integers $C_i$ for $1 \le i \le n_1$ such that $b+ \sum^{n_1}_{i=1} C^{'}_i a_i \in V-V_1$ for $0 \le C^{'}_i \le C_i$. For sake of contradiction suppose there exist k and $0 \le K_i \le C_i$ for $i \ne k$, such that $b+ \sum^{n_1}_{i=1 \atop i \ne k} K_i a_i + (C_k +1)a_k \in V_1$. Now by assumption $b+ \sum^{n_1}_{i=1 \atop i \ne k} K_i a_i + (C_k )a_k \in V-V_1$. Also since $b+a_k \notin V_1$ either $C_k>0$ or there exist $K_i>0$ for some $1 \le i \le n_1$, $i \ne k$, denote $K_c$. Case 1: $(C_k >0)$ Since $b+ \sum^{n_1}_{i=1,i \ne k} K_i a_i + C_k a_k \in V-V_1$ and $b+ \sum^{n_1}_{i=1,i \ne k} K_i a_i + C_k a_k +a_k \in V_1$, by $Corollary$ 2.3, $b+ \sum^{n_1}_{i=1,i \ne k} K_i a_i + (C_k )a_k+a_j \in V_1$ for $1 \le j \le n_1$ and notice these are $n_1$ distinct vertices of $V_1$. So there exist $l$ such that $a_k \equiv b+ \sum^{n_1}_{i=1 \atop i \ne k} K_ia_i + C_k a_k+a_l$. Hence $b+ \sum^{n_1}_{i=1 \atop i \ne k} K_ia_i + (C_k-1) a_k+a_l \equiv 0$, but since $C_k>0$ by our assumption $b+ \sum^{n_1}_{i=1 \atop i \ne k} K_ia_i + (C_k-1) a_k \in V-V_1$. Thus $b+ \sum^{n_1}_{i=1 \atop i \ne k} K_ia_i + (C_k-1) a_k+a_l \in \cal F$, a contradiction. Case 2: $(C_k=K_k=0)$ So $K_c>0$ for some $c \ne k$. So by $Corollary$ 2.3, $b+ \sum^{n_1}_{i=1 \atop i \ne c} K_ia_i + K_c a_c+a_j \in V_1$ for $1 \le j \le n_1$, and also notice they are $n_1$ distinct elements. Since $\vert V_1 \vert = n_1$ and $a_c \in V_1$, there exist $l$ such $a_c \equiv b+ \sum^{n_1}_{i=1 \atop i \ne c} K_ia_i + K_c a_c+a_l$. Therefore $b+ \sum^{n_1}_{i=1 \atop i \ne c} K_ia_i + (K_c-1) a_c+a_l \equiv 0$, a contradiction by the previous argument. Hence $b+ \sum^{n_1}_{i=1} C_ia_i \in V-V_1$ for all $C_i \ge 0$. Now since $d=gcd (a_1,...,a_{n_1})$, by $Observation$ 2.1, there exist nonnegative integers $K_i$ for $1 \le i \le n_1$ such that $d \equiv \sum^{n_1}_{i=1} K_ia_i$. Then it follows that $b+ \sum^{n_1}_{i=1} K_ia_i \equiv b+d \in V-V_1$. Since $b+ \sum^{n_1}_{i=1} C_ia_i \in V-V_1$ for all $C_i \ge 0$, then for all $l \ge 0$, $b+ l\sum^{n_1}_{i=1} K_ia_i \equiv b+ld \in V-V_1$. So there must exist i,j where $i \ne j$ such that $b+id \equiv b+jd$, since otherwise $\vert V-V_1 \vert = \infty$. From whence we conclude that there exist $L \in \hbox{Z\kern-.35em\hbox{Z}}^+$ such that $(L+1)d \equiv \cal Z$, and so for any $i\in \hbox{Z\kern-.35em\hbox{Z}}$, $b+ id \equiv b+ld$ for some nonnegative integer $l$, thus $b+id$ $(mod$ ${\cal Z}) \in V-V_1$. $\Box$

The following lemma is the major result in this paper. With it, $Lemma$ 2.8 shows $K_{n,m}$ with $m>n \ge 3$ is not a MSG when $m <2n$.

Lemma 2.7   Suppose $K_{n_1,n_2,...,n_m}$ is a MSG, i.e. $V =\cal F$, with $V_1$ and $V_2$ partite sets, and $\vert V_2 \vert = n_2 \ge \vert V_1 \vert = n_1 \ge 3$. Let $V_1 =\{ a_1,a_2,...,a_{n_1} \}$ with $gcd(a_1,a_2,...,a_{n_1})=d$. If $n_2>n_1$, there exist $b \in V_2$ such that for all $i\in \hbox{Z\kern-.35em\hbox{Z}}$, $b+id \in V_2$ .

Proof. Since for all $b \in V_2$, $0 < b< \cal Z$, then $2b \equiv 0$ implies $b = {{\cal {Z}} \over {2}}$. Since $n_2 \ge 3$, we can chose a $b \in V_2$ such that $2b \not \equiv 0$. Assume $V_1=\{C_1d,C_2d,...,C_{n_1}d\}$. By $Lemma$ 2.6, for all $i\in \hbox{Z\kern-.35em\hbox{Z}}$, $b+id \in V-V_1$ and there exist a $L \in \hbox{Z\kern-.35em\hbox{Z}}^+$ such that $(L+1)d \equiv 0$. Let $L$ be the smallest such positive integer. Suppose there exist j such that $b+jd \notin V_2$. THEN WE ARE GOING TO SHOW $n_1=n_2$. We first establish $2b+C_1d \in V_1$, $b+C_1d \notin V_2$, and $b+2C_1d,3b+2C_1d \in V_2$. Since $\vert R \vert =0$, $\{b,b+jd\} \in E$. So $2b+jd \in V$. Assume for $k \in \hbox{Z\kern-.35em\hbox{Z}}^+$, there exist an $i$ such that $kb+id \in V$. Now either $kb+id \in V_2$ or $kb+id \notin V_2$. Hence either $\{kb+id,b+jd\} \in E$ or $\{kb+id,b\} \in E$. Thus either $(k+1)b+(i+j)d \in V$ or $(k+1)b+id \in V$. Therefore by induction for all $k \in \hbox{Z\kern-.35em\hbox{Z}}^+$ there exist a $i$ such that $kb+id \in V$. This implies that there must exist $K>N>0$, and $i,j \in \hbox{Z\kern-.35em\hbox{Z}}$ such that $Kb+id \equiv Nb+jd$. We wish to show that there exist a $J \in \hbox{Z\kern-.35em\hbox{Z}}^+$ such that $(J+1)b \equiv 0$. So $(K-N)b \equiv (j-i)d$. If $j=i$, since $b \ne 0$, we have a $J>0$ such that $(J+1)b \equiv 0$. If $j \ne i$, $b+k(K-N)b \equiv b+k(j-i)d \in V-V_1$ for all $k \in \hbox{Z\kern-.35em\hbox{Z}}$. Hence there must exist $r,s \in \hbox{Z\kern-.35em\hbox{Z}}^+$ with $r>s$, such that $b+r(K-N)b \equiv b+s(K-N)b$. Thus $(r-s)(K-N)b \equiv 0$. Since $r>s$ and $K>N$, there a exist a $J \in Z^+$ such that $(J+1)b \equiv 0$. Let $J$ be the smallest such positive integer. By the above argument there exist a k such that $Jb+kd \in V$. Hence $(J+1)b \equiv (L+1)d \equiv 0$. Suppose for any $l \in Z$, that $Jb+ld \in V_1$. Now $b+(C_1+C_2-l)d \in V-V_1$. Then $\{Jb+ld,b+(C_1+C_2-l)d\} \in E$ which implies $(C_1+C_2)d \in V$, a contradiction. So $Jb+ld \in V-V_1$. Thus $Jb+kd \notin V_1$. Whence $\{Jb+kd,C_1d\} \in E$, and $Jb+kd+C_1d \in V$. By the previous argument $Jb+kd+C_1d \in V-V_1$. Repeating one can see that $Jb+kd+ \sum^{n_1}_{i=1}K_iC_id \in V-V_1$ for all $K_i \ge 0$. Since $d=gcd (a_1,...,a_{n_1})$, by $Observation$ 2.1, there exist nonnegative integers $K^{'}_i$ for $1 \le i \le n_1$ such that $d \equiv \sum^{n_1}_{i=1} K^{'}_ia_i$. Therefore for $l \ge 0$, $Jb+kd+l\sum^{n_1}_{i=1} K^{'}_ia_i \equiv Jb+kd+ld \in V-V_1$. Since we have $L$ as the smallest positive integer such that $(L+1)d \equiv 0$, then $Jb+id \in V-V_1$ for $0 \le i \le L$ are $L+1$ distinct elements. We wish to show for all $C_id$, $C_jd \in V_1$, that $b+C_id$, $J+C_jd$ are in the same partite set distinct from $V_2$. Denote $V_3$, the partite set containing $b+C_1d$. Now if $b+C_1d \equiv Jb+C_id$ for some $i$ then it follows that $Jb+C_id \in V_3$. Suppose $b+C_1d \not \equiv Jb+C_id$ for $i \ne 1$. Then $Jb+C_id \in V_3$ since otherwise $\{Jb+C_id,b+C_1d\} \in E$ implies $C_id +C_1d \in \cal F$ for $i \ne 1$. Hence $Jb+C_id \in V_3$ for $i \ne 1$. Since $n_1 \ge 3$, for $b+C_jd$ where $j \ne 1$, there exist $C_ld$ such that $C_ld \ne C_jd$, $C_ld \ne C_1d$. So $Jb+C_ld \in V_3$, by the previous argument, implies $b+C_jd \in V_3$. Hence $b+C_jd \in V_3$ for all $C_jd \in V_1$. Finally, we have $b+C_2d \in V_3$ implies $Jb+C_1d \in V_3$. Now there exist an $i$ such that $Jb+C_id \not \equiv b$. Since $Jb+C_id+b \equiv C_id$, it follows that $\{Jb+C_id,b\} \in E$. So $V_3$ is a different partite set then $V_2$ and $V_3$ contains $b+C_id, Jb+C_jd$ for all $C_id,C_jd \in V_1$. Therefore we have $\{b,b+C_id\} \in E$ implying that $2b+C_id \in V$. Now $\{b+C_id,b+C_jd\} \notin E$ for $i \ne j$. So $2b+C_id+C_jd \notin V$, for $i \ne j$. So $2b+C_id \in V_1$ for all $C_id \in V_1$. The vertices $Jb$, $Jb+(C_i+C_j)d \in V_2$ for $i \ne j$, since these vertices must not be adjacent to b. So $b+C_id+C_jd \in V_2$ for $i \ne j$, because they can not be adjacent to $Jb$. Now we established $b+C_1d \notin V_1$. Then $\{b+C_1d,C_1d\} \in E$, and so $b+2C_1d \in V$. Since $2b \not \equiv 0$, then $C_1d \not \equiv 2b+C_1d$. Notice $2b+2C_1d \notin \cal F$ implies $\{b+2C_1d,b\} \notin E$ implying $b+2C_1d \in V_2$. Also since $C_1d \not \equiv 2b+C_1d$, we have $b+(C_1d)+(2b+C_1d) \equiv 3b+2C_1d \in V_2$. So we have established $2b+C_1d \in V_1$, $b+C_1d \notin V_2$, and $b+2C_1d,3b+2C_1d \in V_2$. We wish to establish $n_1=n_2=\vert V_3 \vert$. By assumption $n_2 \ge n_1$. Let $f:V_2 \rightarrow V_1$ by $f(x)=x+b+C_1d$. Pick $x \in V_2$. Then $\{x,b+C_1d\} \in E$, and so $x+b+C_1d \in V$. Now if $x+b+C_1d \notin V_1$, then $\{x+b+C_1d,C_1d\}$, $\{x+b+C_1d,2b+C_1d\} \in E$. Therefore $x+b+2C_1d$, $x+3b+2C_1d \in V$. Well $2b \not \equiv 0$ implies $b+2C_1d \not \equiv 3b+2C_1d$. Hence either $\{x,b+2C_1d\} \in E$ or $\{x,3b+2C_1d\} \in E$, which can not happen. Therefore $x+b+C_1d \in V_1$. If $f(x) \equiv f(y)$ then $x+b+C_1d \equiv y+b+C_1d$, and so $x \equiv y$. So f is an injection. Thus $n_1=\vert V_1 \vert \ge \vert V_2 \vert=n_2$, a contradiction. $\Box$

The next lemma is cited in $Theorem$ 2.12 and $Theorem$ 2.13. These theorems $\rho (K_{n,m})$ when $m>n \ge 3$ and m is even.

Lemma 2.8   If $K_{n_1,n_2,...,n_m}$ is a MSG, i.e. $V =\cal F$, with $V_1$ and $V_2$ partite sets $\vert V_2 \vert = n_2 > \vert V_1 \vert = n_1 \ge 3$, then $n_2 \ge 2n_1$. If $a_1, 2a_1 \in V_1$, then $n_2 \ge 3n_1-3$.

Proof. Denote $V_1=\{C_1d,C_2d,...,C_{n_1}d\}$ where $d=gcd(C_1d,C_2d,...,C_{n_1}d)$. By $Lemma$ 2.7, there exist $b \in V_2$ such that $b+id \in V_2$ for $0 \le i \le L$ where $L$ is the smallest positive integer such that $(L+1)d \equiv 0$. Thus $b+id \in V_2$ for $0 \le i \le L$ are $L+1$ distinct vertices implying $n_2 \ge L+1$. Since $L$ is the smallest positive integer such that $(L+1)d \equiv 0$ we have at most $L+1$ distinct multiples of d modulo $\cal Z$. Now $\{C_1d,C_id\} \notin E$, so $C_1d+C_id \notin \cal F$ for $2 \le i \le n_1$. If $C_1d+C_id \equiv C_1d+C_jd$, then $C_id \equiv C_jd$. So $C_jd, \{C_1+C_i\}d$ for $1 \le j \le n_1$, $2 \le i \le n$ are $2n_1-1$ distinct multiples of d modulo $\cal Z$. So $n_2 \ge L+1 \ge 2n_1-1$. If $C_1d +C_jd \equiv 2C_1d$, then $C_jd \equiv C_1d$. Hence if $2C_1d \notin V_1$, then $n_2 \ge L+1 \ge 2n_1$. Suppose $2C_1d \equiv C_2d \in V_1$. We will establish $C_1d$, $2C_1d$, $3C_1d$, $C_id$, $C_1d+C_id$, $2C_1d+C_id$ for $3 \le i \le n_1$ are $3n_1-3$ distinct multiples of d mod $\cal Z$. Now $C_1d \not \equiv C_id$, $2C_1d \not \equiv C_id$ for $3 \le i \le n_1$. Also $3C_1d$, $C_1d+C_id$, $2C_1d+C_id \notin \cal F$ for $3 \le i \le n_1$. Likewise $C_1d$, $2C_1d$, $C_id \notin \{3C_1d$, $C_1d+C_jd$, $2C_1d+C_jd \}$ $(mod$ $\cal Z)$ for $3 \le j \le n_1$, $3 \le i \le n_1$. If $3C_1d \equiv C_1d+C_id,$ then $2C_1d \equiv C_id$. Notice if $3C_1d \equiv 2C_1d+C_id$ then $C_1d \equiv C_id$. So $3C_1d \notin \{C_1d+C_id$, $2C_1d+C_id \} \, (mod \, \cal Z)$ for $3 \le i \le n_1$. Finally $C_1d+C_id \not \equiv 2C_1d+C_jd$, since $C_id \not \equiv C_1d +C_jd$. Hence we have $1+1+1+(n_1-2)+(n_1-2)+(n_1-2)=3n_1-3$ distinct multiples of d mod $\cal Z$. So $n_2 \ge L+1 \ge 3n_1-3 \ge 2n_1$ when $n_1 \ge 3$. $\Box$

Corollary 2.9   If $K_{n_1,n_2,...,n_m}$ is a MSG with $n_1>n_2>...>n_{m-1}>n_m \ge 3$, then $n_1 \ge 2n_2 \ge 2^2 n_3 \ge...\ge 2^{m-2}n_{m-1} \ge 2^{m-1} n_m$.

Proof. The result follows by induction using $Lemma$ 2.8. $\Box$

The next theorem is a special case needed for $Theorem$ 2.12. This result was first proved by Miller, Ryan, Sutton, and Slamin in [#!mrss!#].

Theorem 2.10   $K_{n,n}$ is not a MSG for $n \ge 3$.

Proof. Denote partitions $V_1=\{a_1,a_2,...,a_n\}$ and $V_2 =\{b_1,b_2,...,b_n\}$. By $Lemma$ 2.5, if $K_{n,n}$ is a MSG, with $a_j \in V_1$ then for all $b_i \in V_2$, $a_j+b_i \in V-V_2$. Likewise for $b_j \in V_2$, for all $a_i \in V_1$, $a_i+b_j \in V-V_1$. Since both can not be true $a_j+b_i \in R$, for all $a_j \in V_1$, $b_i \in V_2$. $\Box$

The following theorem is used in $Theorem$ 2.12.

Theorem 2.11   If $K_{n,m}$ is not a MSG, with $n \le m$ then $n \le \rho(\hbox{I\kern-.25em\hbox{K}}_{n,m}) \le m$.

Proof. Denote partitions $V_1=\{a_1,a_2,...,a_n\}$ and $V_2 =\{b_1,b_2,...,b_m\}$. By assumption there exist $a_i$, $b_j$ such that $a_i+b_j \in R$. Now by $Lemma$ 2.5, $b_j+a_i \in R$ for $1 \le i \le n$. So $\rho(\hbox{I\kern-.25em\hbox{K}}_{n,m}) \ge n$. We now give a labelling for which $\vert R \vert =m$. Let $a_i=(i-1)10+7$, $b_i=(i-1)10+9$, $r_i=(i-1)10+6$ with ${\cal {Z}} = 10m$. Then $R = \{6,16,...,10(m-1)+6\}$. Notice $a_i+b_j = (i+j-2)10+16 \in R$, $a_i+a_j=(i+j-2)10+14 \notin {\cal {F}}$, $b_i+b_j=(i+j-2)10+18 \notin {\cal {F}}$, $r_i+r_j =(i+j-2)10+12 \notin {\cal {F}}$, $a_i+r_j= (i+j-2)10+13 \notin {\cal {F}}$, and finally, $b_i+r_j=(i+j-2)10+15 \notin \cal F$. Thus $\rho(\hbox{I\kern-.25em\hbox{K}}_{n,m}) \le m$. $\Box$

Figure: $\rho(\hbox{I\kern-.25em\hbox{K}}_{5,11}) \le 11 \quad (mod \quad 110)$

The next three theorems, $Theorem$ 2.12, $Theorem$ 2.13, and $Theorem$ 2.14, show $K_{n,m}$ is a mod sum graph when $m$ is even and $m \ge 2n$ or when $m$ is odd and $m \ge 3n-3$ and $\rho (K_{n,m})=n$ when $3 \le n \le m < 2n$.

Theorem 2.12   $\rho (K_{n,m})=n$, if $3 \le n \le m < 2n$.

Proof. By $Lemma$ 2.8, $K_{n,m}$ is not a MSG since $m <2n$. By $Theorem$ 2.11, $\rho(K_{n,m}) \ge n$. Denote partitions $V_1=\{a_1,a_2,...,a_n\}$ and $V_2 =\{b_1,b_2,...,b_m\}$. We now give a labelling for which $\vert R \vert =n$. Let $a_i=(i-1)10+9$, $b_i=(i-1)10+6$ for $1 \le i \le n$, $b_i=(i-1)10+7$ for $n<i \le m$. Let $r_i=(i-1)10+5$ with ${\cal {Z}} = 10n$. Then $R = \{5,15,...,10(n-1)+5\}$. Notice if $j \le n$, then $a_i+b_j = (i+j-2)10+15 \in R$, and if $j>n$, then $a_i+b_j = (i+j-2)10+16 \in V_2$. Now for any $i$,$j$, $a_i+a_j=(i+j-2)10+18 \notin {\cal {F}}$, for $i,j \le n$, $b_i+b_j=(i+j-2)10+12 \notin {\cal {F}}$, for $i \le n$, $j>n$, $b_i+b_j=(i+j-2)10+13 \notin {\cal {F}}$, and for $i,j > n$, $b_i+b_j=(i+j-2)10+14 \notin {\cal {F}}$. Also, $r_i+r_j =(i+j-2)10+10 \notin {\cal {F}}$, $a_i+r_j= (i+j-2)10+14 \notin {\cal {F}}$, and finally, for $i \le n$, $b_i+r_j=(i+j-2)10+11 \notin \cal F$, for $i >n$, $b_i+r_j=(i+j-2)10+12 \notin \cal F$. Thus $\rho(\hbox{I\kern-.25em\hbox{K}}_{n,m}) \le n$. $\Box$

Figure: $\rho(\hbox{I\kern-.25em\hbox{K}}_{4,7})=4 \quad (mod \quad 40)$

Theorem 2.13   If m is even and $m\ge4$, then $K_{n,m}$ with $m \ge n$ is a MSG if and only if $m \ge 2n$.

Proof. $\Longrightarrow$ By $Theorem$ 2.10, $K_{n,m}$ is not a MSG if $n=m$. By $Lemma$ 2.8, if $K_{n,m}$ is MSG with $m>n$, then $m \ge 2n$. $\Longleftarrow$ Assume $m \ge 2n$ with m even. Let $V_1$ and $V_2$ be partite sets. Let $V_1 \subset \{d,3d,...,(m-1)d \}$, $V_2= \{1,1+d,1+2d,...,1+(m-1)d\}$, $d=4$, and ${\cal {Z}}=dm=4m$. Pick $(2i+1)d \in V_1$ and $1+jd \in V_2$, then $\{(2i+1)d,1+jd\} \in E$ since $(2i+1)d+1+jd = 1+(jd+2(i+1)d) \, (mod \, dm)=1+kd$ for some k. Pick $(2i+1)d$, $(2j+1)d \in V_1$. Now $[(2i+1)d+(2j+1)d]=2(i+j+1)d \, (mod \, dm)=2kd$ when m is even. Since $2kd \notin \cal F$, $\{(2i+1)d,(2j+1)d\} \notin E$. Pick $1+id$, $1+jd \in V_2$. Now $(1+id+1+jd) \, (mod \, dm)=2+kd$ for some k. Also $2+kd \ne ld$, since $2=(k-l)d \, (mod \, dm)$ implies $d<4$. Likewise $2+kd \ne 1+ld$, since $1=(k-l)d \, (mod \, dm)$ implies $d<4$. Thus $1+id+1+jd \notin \cal F$ which in turn means $\{1+id,1+jd\} \notin E$. $\Box$

Figure: K $_{4,8} \quad (mod \quad 32)$

Theorem 2.14   If m is odd and $m\ge 3$, then $K_{n,m}$ with $m \ge 3n-3$ is a MSG.

Proof. Let $L= \lfloor {m \over 3} \rfloor +1$. Then $L$ is the largest integer such that $3L-3 \le m$. So if $3n-3 \le m$, then $3n-3 \le 3L-3$, which implies $n \le L$. Either $L=2K+1$ or $L=2K$. Case 1: (L=2K+1) Let $V_1 \subset \{ d,3d,..., (l-2)d, (m-l)d, (m-l+2)d,...,(m-3)d,(m-1)d \}$, and $V_2= \{1,1+d,1+2d,...,1+(m-1)d\}$ where $d=4$ and $dm = \cal Z$. So for any $s \in V_1$, $r \in V_2$, $s+r \in V_2$, and for any $s,r \in V_2$, $s+r \notin V$. Denote $a_i =(2i-1)d$ for $1 \le i \le K$, $b_i =(m-2i+1)d$ for $1 \le i \le K+1$. Then the $a_i$ are odd multiples of d and the $b_i$ are even multiples of d. Now $a_1< a_2<...< a_K <b_{K+1} < b_K<...<b_1$. Therefore for any $a_i$, $a_j \in V_1$ for $i \ne j$, $2(i+j-1)d=a_i+a_j \le a_{K-1}+a_K \le (2L-6)d < (2L-2)d \le (m-L+1)d <dm$. So $a_i+a_j = 2(i+j-1)d \not \equiv a_h=(2h-1)d$ for any h, and $a_i+a_j < (m-L)d=b_{K+1}$. Hence $a_i+a_j \notin V_1$, and $a_i+a_j \notin V_2$. Pick $a_i$, $b_j \in V_1$. Now $a_i+b_j=(2i-1)d +(m-2j+1)d \equiv (m-2(i-j))d$. If $a_i+b_j< dm$, then $a_i+b_j$ is and odd multiple of d, and $a_K<a_i+b_j$, so $a_i+b_j \notin V_1$. If $a_i+b_j> dm$, then $a_i+b_j < a_i \, (mod \, dm) < b_{K+1}$, and $a_i+b_j$ is an even multiple. So $a_i+b_j \notin V_1$, and $a_i+b_j \notin V_2$. Pick $b_i$, $b_j \in V_1$ with $i \ne j$. Then $dm< (2m-2L+2)d=(2m-4K)d=b_K+b_{K+1} \le b_i+b_j<2md$. So $(2m-2L+2)d \equiv (m-2L+2)d$, and $a_K=(L-2)d < (L-1)d\le (m-2L+2)d< dm$. So $b_i+b_j \notin V_1$, and $b_i+b_j \notin V_2$. Case 2: (L=2K) Let $V_1 \subset \{ d,3d,..., (l-1)d, (m-l+1)d, (m-l+3)d,...,(m-3)d,(m-1)d \}$, and $V_2= \{1,1+d,1+2d,...,1+(m-1)d\}$ where $d=4$ and $dm = \cal Z$. Denote $a_i =(2i-1)d$ for $1 \le i \le K$, $b_i =(m-2i+1)d$ for $1 \le i \le K$. Now $a_1< a_2<...< a_K <b_K < b_{K-\lq }<...<b_1$. Similarly to the previous argument, we can show the desired properties results. $\Box$

Figure: $\hbox{I\kern-.25em\hbox{K}}_{6,15} \quad (mod \quad 60)$