A survey of face-antimagic evaluations of graphs

NEW

Problem: Reconstruct the open problem as follows. For integers $m,n\ge1$, let $H_n^m$ be the standard honeycomb plane map with $m$ rows and $n$ columns of hexagons. A type $(1,1,1)$ labeling is a bijection from $V(H_n^m)\cup E(H_n^m)\cup F(H_n^m)$ to $\{1,\dots, |V|+|E|+|F|\}$. The weight of a face is the sum of its own label and the labels of all boundary vertices and edges. The task asks for further values of $d$ for which the 6-sided face weights form an arithmetic progression with common difference $d$. The survey records $d=2,4$ for even $n$, and $d=1,2,3,4$ for odd $n$, so “other” naturally asks for an additional value; below $d=6$ is obtained for all $m,n$.

Result: For every $m,n\ge1$, $H_n^m$ has a type $(1,1,1)$ $6$-antimagic labeling.

Use the usual coordinate model with internal faces $h_{i,j}$, $0\le i<m$, $1\le j\le n$, and let

$$N=|V|+|E|+|F|=6mn+4m+4n .$$

Index the vertices as $U_{a,b}\neq U_{0,0}$, $V_{a,b}\neq V_{m,n}$, and the three edge directions as $A_{a,b},B_{a,b},C_{a,b}$, so each face $h_{i,j}$ contains

$$\begin{aligned} &U_{i,j},U_{i+1,j},U_{i+1,j-1},\\ &V_{i,j},V_{i+1,j-1},V_{i,j-1},\\ &A_{i,j},A_{i+1,j-1},B_{i,j},B_{i,j-1},C_{i+1,j},C_{i,j}. \end{aligned}$$

Let $r(i,j)=in+j-1$. Assign odd labels to $U,B,C$ and even labels to $V,A$, the internal faces, and the outer face:

$$\lambda(h_{i,j})=2+2(s_V+s_A)+2r(i,j),$$

where $s_V=mn+m+n$, $s_A=mn+m+n-1$, and set the outer face label to $N$. Choose the vertex/edge labels in the corresponding odd/even blocks so that the ranks of $U,A,C$ increase lexicographically, while those of $V,B$ decrease lexicographically. These blocks have exactly the required sizes:

$$s_U+s_B+s_C=s_V+s_A+mn+1=N/2.$$

Thus all labels $1,\dots,N$ are used exactly once.

A direct summation over the twelve boundary elements of $h_{i,j}$ gives

$$\sum_{x\subset \partial h_{i,j}}\lambda(x)=K+4r(i,j)$$

for a constant $K$ independent of $i,j$. Therefore

$$w(h_{i,j})=K+4r(i,j)+\lambda(h_{i,j}) =K'+6r(i,j).$$

Hence the internal hexagonal face weights are

$$K',K'+6,\dots,K'+6(mn-1),$$

an arithmetic progression with common difference $6$. If $mn>1$, the exterior face is the unique non-hexagonal face and imposes no further condition. If $mn=1$, label the two faces by labels differing by $6$, e.g. $1$ and $7$; their common boundary sum is the same, so the two 6-sided face weights differ by $6$.

Citation: The problem and definitions are from Bača et al., “A survey of face-antimagic evaluations of graphs,” Australas. J. Combin. 69(3) (2017), 382–393, Open Problem 2. The $d=6$ construction above is given here.