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

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

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:

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:

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

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

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

Hence the internal hexagonal face weights are

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.