Let \(G\) be a graph. We introduce the balanced antimagic labeling as an analogue to the antimagic labeling. A \(k\)-total balanced antimagic labelling is a map \(c\colon V (G)\cup E(G) \to \{1,2,\ldots,k\}\) such that: the label classes differ in size by at most one, each vertex \(x\) is assigned the weight \(w(x)={c}(x)+\sum\limits_{x\in e}{c}(e)\), and \(w(x)\neq w(y)\) for \(x\neq y\).
We present several properties of balanced antimagic labeling. We also derive such a labeling for complete graphs and complete bipartite graphs.
For standard terms and notation in graph theory, the reader is referred to the textbook by Diestel [4]. An introduction to magic- and anti-magic-type labelings can be found in the monograph by Bača et al. [2].
An antimagic labeling of a graph \(G=(V,E)\) is a one-to-one correspondence between \(E(G)\) and \(\{1,\ldots,|E(G)|\}\) such that the vertex-sum (i.e., the sum of the labels assigned to edges incident to a vertex) for distinct vertices are different. It was conjectured by Hartsfield and Ringel that every tree other than \(K_2\) has an anti-magic labeling [5]. Similarly, a total antimagic labeling is a one-to-one correspondence between \(V(G)\cup E(G)\) and \(\{1,\ldots,|E(G)\cup V(G)|\}\) such that all vertex weights are pairwise distinct, where the vertex weight is the sum of the label of that vertex and labels of all edges incident with the vertex [1]. Miller, Phanalasy and Ryan proved that all graphs admit total antimagic labeling [6].
A \(k\)-coloring of a graph \(G\) is called balanced, if the label classes differ in size by at most one. The best know balanced labeling is a cordial labeling introduced by Cahit [3].
In this paper we combine these two types of concepts and introduce a new labeling called total balanced antimagic labeling. A graph \(G\) is \(k\)-total balanced antimagic if there exists a labelling \(c\colon V (G)\cup E(G) \to \{1,2,\ldots,k\}\) such that:
\(\bullet\) the label classes differ in size by at most one,
\(\bullet\) each vertex \(x\) is assigned the weight \(w(x)={c}(x)+\sum\limits_{x\in e}{c}(e)\), and
\(\bullet\) \(w(x)\neq w(y)\) for \(x\neq y\).
Note that although we call \(c\) antimagic it is not necessary a bijection. Moreover, for \(k=|E(G)\cup V(G)|\), then \(k\)-total balanced antimagic labeling is just total antimagic labeling.
For \(c\colon V (G)\cup E(G) \to \{1,2,\ldots,k\}\) let \(c_i=|c^{-1}(i)|\) for \(i\in\{1,2,\ldots,k\}\). We start this section with some basic observations.
Observation 2.1. If \(k\geq |V(G)|\), then a graph \(G=(V,E)\) is \(k\)-total balanced antimagic.
Proof. We will start by labeling the edges of \(G\) in a balanced way, i.e. the label classes differ in size by at most one. Without loss of generality, assume that the temporary weights of vertices fulfill \(w'(v_i)=\sum\limits_{v_i\in e}c(e)\leq w'(v_j)=\sum\limits_{v_j\in e}c(e)\) for all \(1\leq i<j\leq n\) with \(n=|V(G)|\). We next label vertices \(v_i\), since the labeling of the edges is balanced and \(k\geq n\) we can do that in such a way that \(c(v_i) < c(v_j)\), for \(1 \leq i<j \leq n\). Under this total labeling, it is clear that \(w(v_i)=w'(v_i)+c(v_i) < w(v_j)=w'(v_j)+c(v_j)\), for \(1 \leq i<j \leq n\). ◻
From the above observation, we obtain a corollary:
Corollary 2.2. If a connected graph \(G=(V,E)\) has an antimagic labeling, then it is \(k\)-total balanced antimagic for \(k=|E(G)|\).
Proof. By Observation 2.1 we can assume that \(G = (V,E)\) is a tree, thus \(k=|V(G)|-1=n-1\). Let \(c\) be an antimagic labeling of \(G\) such that \(w(v_i)=\sum\limits_{v_i\in e}c(e)<w(v_j)=\sum\limits_{v_j\in e}c(e)\) for all \(1\leq i<j\leq n\) with \(n=|V(G)|\). We next label vertices \(v_i\) with \(i\) for \(i\in\{1,2,\ldots,n-1\}\) and \(c(v_{n})={n-1}\). Under this total labeling, it is clear that \(w(v_i)=w'(v_i)+c(v_i) < w(v_j)=w'(v_j)+c(v_j)\), for \(1 \leq i<j \leq n\). ◻
In this paper, we will focus on an open problem that was stated by the first author during IWOGL 2024:
Problem 2.3. Characterize \(k\)-regular \(k\)-total balanced antimagic graphs.
We will start with an easy observation:
Observation 2.4. If a \(k\)-regular graph \(G=(V,E)\) has a \(k\)-total balanced antimagic labeling, then \(|V(G)|\leq k^2\).
Proof. Assume that \(G\) admits such a labeling, then the \(w(x)\in\{k+1,k+2,\ldots,(k+1)k\}\) for any \(x\in V(G)\), as \(|\{k+1,k+2,\ldots,(k+1)k\}|=k^2\) therefore \(|V(G)|\leq k^2\). ◻
Theorem 2.5. The complete graph \(K_{k+1}\) admits \(k\)-total balanced antimagic labeling if and only if \(k\not\in\{1,2\}\).
Proof. One can easily check that the graph \(K_{k+1}\) is not \(k\)-total balanced antimagic for \(k\in{1,2}\). Suppose now, that \(k\geq 3\). Note that \(c_i\in\left\{\lfloor \frac{(k+1)(k+2)}{2k}\rfloor,\lceil \frac{(k+1)(k+2)}{2k}\rceil \right\}\), thus for \(k=3,\ c_i\in \{3,4\}\) and for \(k\geq 4\), \(c_i<k\). Let \(A=\left\{c^{-1}(i): c_i = \lfloor \frac{(k+1)(k+2)}{2k}\rfloor\right\}\) and \(B=\left\{c^{-1}(i): c_i =\lceil \frac{(k+1)(k+2)}{2k}\rceil\right\}\). Observe that \(A \neq \emptyset\) and \(B \neq \emptyset\). We will label the graph \(K_{k+1}\) in such a way that \(c^{-1}(k-1)\in A\) and \(c^{-1}(k)\in B\). We will start by labeling the edges of \(K_{k+1}\), where each color \(i\in \{1,2,\ldots,k-1\}\) will be used \((c_i-1)\) times and color \(k\) will be used \((c_k-2)\) times. Moreover, we pick a vertex \(v_{k+1}\in V(K_{k+1})\), and all incident edges we label with the highest possible labels. Thus the temporary weights of the vertices can be put into a sequence: \(w'(v_1)=\sum\limits_{v_1\in e}f(e) \leq w'(v_2 )=\sum\limits_{v_2\in e}f(e)\leq \ldots \leq w'(v_k)=\sum\limits_{v_k\in e}f(e)<w(v_{k+1})=\sum\limits_{v_{k+1}\in e}f(e)\). We next label vertices \(v_i\) with \(i\) for \(i\in\{1,2,\ldots,k\}\) and \(v_{k+1}=k\). Under this total labeling, it is clear that \(w(v_i) < w(v_j)\), for \(1 \leq i<j \leq k+1\). An example of such labeling for \(K_4\) is shown in Figure 1, where the vertex \(v_4\) is black.
◻
Theorem 2.6. The complete graph \(K_{k,k}\) admits \(k\)-total balanced antimagic labeling if and only if \(k\neq 1\).
Proof. One can easily check that a graph \(K_{1,1}\) is not \(1\)-total balanced antimagic. Let \(V=\{v_1,\ldots,v_k\}\) and \(U=\{u_1,\ldots,u_k\}\) be partition sets
for \(G=K_{k,k}\).
For \(k\geq 2\), we will show an
explicit \(k\)-total balanced antimagic
labeling of \(G\), following the next
steps:
1. We will give a \(k\)-balanced labeling of the edges of \(G\) , where each label is used exactly \(k\) times.
2. We will give a \(k\)-labeling for the vertices of \(G\).
3. We will show that for each pair of vertices \(u\not= v\) in \(G\), \(w(u)\not= w(v)\).
Case 1. \(k=2m\)
Set \[f(v_iu_j)=\begin{cases} \left\lfloor \frac{j+1}{2}\right\rfloor,&\text{for}\;\;i\in\{1,3,\ldots,2m-1\},\\ 2m+1-\left\lfloor \frac{j+1}{2}\right\rfloor,&\text{for}\;\;i\in \{2,4,\ldots,{2}m\}. \end{cases}\]
Then:
1. For any \(i\in\{1,3,\ldots,2m-1\}\), \(\sum\limits_{j=1}^k f(v_iu_j)= m(m+1)\);
2. for any \(i\in\{2,4,\ldots,2m\}\),\(\sum\limits_{j=1}^k f(v_iu_j)= m(3m+1)\); and
3. for any \(j\in\{1,2\ldots,k\}\), \(\sum\limits_{i=1}^k f(v_iu_j)= m(2m+1)\).
Let us put the following labels to the vertices of \(G\).
\[f(v_i)=\begin{cases} \left\lfloor \frac{i+1}{2}\right\rfloor,&\text{for}\;\;i\in\{1,3,\ldots,2m-1\},\\ m+\left\lfloor \frac{j+1}{2}\right\rfloor,&\text{for}\;\;i\in \{2,4,\ldots,2m\}, \end{cases}\] and \[f(u_j)=j\ \text{for}\ j\in\{1,2,\ldots,2m\}.\]
Therefore,
1. For any \(i\in\{1,3,\ldots,2m-1\}\), \(m(m+1)+1\leq w(v_i)\leq m(m+2)\);
2. for any \(i\in\{2,4,\ldots,{2}m\}\), \(m(3m+2)+1\leq w(v_i)\leq 3m(m+1)\); and
3. for any \(j\in\{1,2\ldots,k\}\), \(m(2m+1)+1\leq w(u_j)\leq m(2m+3)\).
Case 2. \(k=2m+1\)
Set \[f(v_iu_j)=\begin{cases} \left\lfloor \frac{j+1}{2}\right\rfloor,&\text{for}\;\;i\in\{1,3,\ldots,2m-1\},\\ 2m+2-\left\lfloor \frac{j+1}{2}\right\rfloor,&\text{for}\;\;i\in \{2,4,\ldots,m\},\\ j ,&\text{for}\;\;i=2m+1. \end{cases}\]
Then
1. For any \(i\in\{1,3,\ldots,2m-1\}\), \(\sum\limits_{j=1}^k f(v_iu_j)= (m+1)(m+2)\);
2. for any \(i\in\{2,4,\ldots,m\}\), \(\sum\limits_{j=1}^k f(v_iu_j)= (m+1)(3m+2)\);
3. for \(i=2m+1\), \(\sum\limits_{j=1}^k f(v_{2m+1}u_j)= (m+1)(2m+1)\); and
4. for any \(j\in\{1,2\ldots,2m+1\}\), \(\sum\limits_{i=1}^k f(v_iu_j)= m(2m+2)+j.\)
Consider the following labels to the vertices of \(G\). \[f(v_i)=\begin{cases} \left\lfloor \frac{i+1}{2}\right\rfloor,&\text{for}\;\;i\in\{1,3,\ldots,2m-3\},\\ m+1, &\text{for}\;\;i=2m-1,\\ m, &\text{for}\;\;i=2m+1,\\ m+1+\left\lfloor \frac{j+1}{2}\right\rfloor,&\text{for}\;\;i\in \{2,4,\ldots,2m\}, \end{cases},\] and \[f(u_j)=j\ \text{for} \ j\in\{1,2,\ldots,2m+1\}.\]
Therefore,
1. For \(i\in\{1,3,\ldots,2m-3\}\), \((m+1)(m+2)+1\leq w(v_i)\leq (m+1)(m+2)+(m-1)\);
2. for \(i=2m-1\), \(w(v_{2m-1})=(m+1)(m+2)+(m+1)\);
3. for \(i=2m+1\), \((m+1)(2m+1)+m\);
4. for \(i\in\{2,4,\ldots,m\}\), \((m+1)(3m+2)+(m+2)\leq w(v_i)\leq (m+1)(3m+2)+ (2m+1)\);
5. for \(j\in\{1,2,\ldots,2m+1\}\), \(w(u_j)=m(2m+2)+2j.\) ◻
The work of the author was supported by the AGH University of Krakow under grant no. 16.16.420.054, funded by the Polish Ministry of Science and Higher Education.