Richard M. Low

Equatorially balanced C4-face-magic labelings on Klein bottle grid graphs

For a graph $G = (V, E)$ embedded in the Klein bottle, let $\mathcal{F}(G)$ denote the set of faces of $G$. Then, $G$ is called a $C_k$-face-magic Klein bottle graph if there exists a bijection $f: V(G) \to \{1, 2, \dots, |V(G)|\}$ such that for any $F \in \mathcal{F}(G)$ with $F \cong C_k$, the sum of all the vertex labelings along $C_k$ is a constant $S$. Let $x_v =f(v)$ for all $v\in V(G)$. We call $\{x_v : v\in V(G)\}$ a $C_k$-face-magic Klein bottle labeling on $G$. We consider the $m \times n$ grid graph, denoted by $\mathcal{K}_{m,n}$, embedded in the Klein bottle in the natural way. We show that for $m,n\ge 2$, $\mathcal{K}_{m,n}$ admits a $C_4$-face-magic Klein bottle labeling if and only if $n$ is even. We say that a $C_4$-face-magic Klein bottle labeling $\{x_{i,j}: (i,j) \in V(\mathcal{K}_{m,n}) \}$ on $\mathcal{K}_{m,n}$ is equatorially balanced if $x_{i,j} + x_{i,n+1-j} = \tfrac{1}{2} S$ for all $(i,j) \in V(\mathcal{K}_{m,n})$. We show that when $m$ is odd, a $C_4$-face-magic Klein bottle labeling on $\mathcal{K}_{m,n}$ must be equatorially balanced. Also when $m$ is odd, we show that (up to symmetries on the Klein bottle) the number of $C_4$-face-magic Klein bottle labelings on the $m \times 4$ Klein bottle grid graph is $2^m \, (m-1)! \, τ(m)$, where $τ(m)$ is the number of positive divisors of $m$. Furthermore, let $m\ge 3$ be an odd integer and $n \ge 6$ be an even integer. Then, the minimum number of distinct $C_4$-face-magic Klein bottle labelings $X$ on $\mathcal{K}_{m,n}$ (up to symmetries on a Klein bottle) is either $(5\cdot 2^m)(m-1)!$ if $n \equiv 0\pmod{4}$, or $(6\cdot 2^m)(m-1)!$ if $n \equiv 2\pmod{4}$.