Total Labelings of Graphs with Prescribed Weights

Bača, Martin; Miller, Mirka; Phanalasy, Oudone; Ryan, Joe; Semaničová-Feňovčíková, Andrea; Sillasen, Anita

doi:10.61091/jcmcc120-33

Abstract

1. Introduction
2. Stars, Paths and Cycles
3. Conclusion
Acknowledgment

References

Journal of Combinatorial Mathematics and Combinatorial Computing

Volume 120
Pages: 367-376

Research article

Total Labelings of Graphs with Prescribed Weights

^¹, ^²,³,⁴, ^²,⁵, ^⁶, ^¹, ^⁷

¹Department of Applied Mathematics and Informatics, Technical University, Košice, Slovakia.

²School of Mathematical and Physical Sciences, The University of Newcastle, Australia.

³Department of Mathematics, University of West Bohemia, Pilsen, Czech Republic.

⁴Department of Informatics, King’s College London, UK.

⁵Department of Mathematics, National University of Laos, Vientiane, Laos.

⁶School of Electrical Engineering and Computer Science, The University of Newcastle, Australia.

⁷Department of Mathematical Sciences, Aalborg University, Aalborg, Denmark.

Received: 10/03/2019
Accepted: 25/03/2020
Published: 30/06/2024

Copyright Link
License

Abstract

The total labeling of a graph $G = (V, E)$ is a bijection from the union of the vertex set and the edge set of $G$ to the set ${1, 2, \dots, | V (G) | + | E (G) |}$ . The edge-weight of an edge under a total labeling is the sum of the label of the edge and the labels of the end vertices of that edge. The vertex-weight of a vertex under a total labeling is the sum of the label of the vertex and the labels of all the edges incident with that vertex. A total labeling is called edge-magic or vertex-magic when all the edge-weights or all the vertex-weights are the same, respectively. When all the edge-weights or all the vertex-weights are different then a total labeling is called edge-antimagic or vertex-antimagic total, respectively.

In this paper we deal with the problem of finding a~total labeling of some classes of graphs that is simultaneously vertex-magic and edge-antimagic or simultaneously vertex-antimagic and edge-magic, respectively.
We show several results for stars, paths and cycles.

Keywords: Edge-magic total labeling, Vertex-magic total labeling, Edge-anti\-ma\-gic total labeling, Vertex-antimagic total labeling

1. Introduction

In this paper we consider finite, simple and undirected graphs. For a graph $G = (V, E)$ we denote the set of vertices $V (G)$ and the set of edges $E (G)$ .

A labeling of a graph $G$ is any mapping that sends certain set of graph elements to a certain set of positive integers or colors. If the domain is the vertex-set, or the edge-set, respectively, the labeling is called a vertex labeling, or an edge labeling, respectively. If the domain is $V (G) \cup E (G)$ then the labeling is called a total labeling. More precisely, for a graph $G$ a bijection $f : V (G) \cup E (G) \to {1, 2, \dots, | V (G) | + | E (G) |}$ is a total labeling of $G$ .

Under the labeling $f$ , the associated edge-weight of an edge $u v$ , $u v \in E (G)$ , is defined by $\begin{aligned} w t_{f} (u v) = f (u) + f (u v) + f (v) . \end{aligned}$

The associated vertex-weight of a vertex $v$ , $v \in V (G)$ , is defined by $\begin{aligned} w t_{f} (v) = f (v) + \sum_{u \in N (v)} f (u v), \end{aligned}$ where $N (v)$ is the set of the neighbors of $v$ .

A labeling $f$ is a called edge-magic total (vertex-magic total) if the edge-weights (vertex-weights) are all the same. If the edge-weights (vertex-weights) are pairwise distinct then the total labeling is called edge-antimagic total (vertex-antimagic total). A graph that admits edge-magic total (edge-antimagic total) labeling or vertex-magic total (vertex-antimagic total) labeling is called edge-magic total (edge-antimagic total) graph or vertex-magic total (vertex-antimagic total) graph, respectively.

In this paper we will use acronyms EMT, VMT, EAT and VAT instead of edge-magic total, vertex-magic total, edge-antimagic total and vertex-antimagic total, respectively.

The subject of EMT graph has its origins in the work of Kotzig and Rosa [1] and VMT graphs were introduced by MacDougall, Miller, Slamin and Wallis in [2], see also [3]. The notion of EAT labeling was introduced by Simanjuntak, Bertault and Miller in [4] as a natural extension of magic valuation defined by Kotzig and Rosa in [1], and VAT labelings of graphs were introduced in [5], see also [6].

There are known characterizations of all EAT and VAT graphs. In [7] Miller, Phanalasy and Ryan proved

Proposition 1 ([7]). All graphs are (super) EAT.

Proposition 2 ([7]). All graphs are (super) VAT.

Since all graphs are EAT and VAT, naturally we can ask whether there exist graphs possessing a labeling that is simultaneously EAT and VAT. Such a labeling is called a totally antimagic total labeling and a graph that admits such a labeling a totally antimagic total graph, for short TAT graph. If, moreover, the vertices are labelled with the smallest possible labels then, as is customary, the labeling is referred to as super. The concept of TAT labeling was given by Bača, Miller, Phanalasy, Ryan, Semaničová-Feňovčíková and Sillasen [8]. In [8] it was proved that complete graphs, paths, cycles, stars, double-stars and wheels are TAT.

The definition of TAT labeling is a natural extension of the concept of totally magic labeling defined by Exoo, Ling, McSorley, Phillips and Wallis in [9]. They showed that such graphs appear to be rare. They proved that the only connected totally magic graph containing a vertex of degree $1$ is $P_{3}$ , the only totally magic trees are $K_{1}$ and $P_{3}$ , the only totally magic cycle is $C_{3}$ , the only totally magic complete graphs are $K_{1}$ and $K_{3}$ , and the only totally magic complete bipartite graph is $K_{1, 2}$ .

In [8] Bača, Miller, Phanalasy, Ryan, Semaničová-Feňovčíková and Sillasen proposed the following open problems.

Problem 1. Find total labeling of some classes of graphs that is simultaneously vertex-magic and edge-antimagic.

Problem 2. Find total labeling of some classes of graphs that is simultaneously vertex-antimagic and edge-magic.

In this paper we will deal with these problems and we will try to find the answers for some classes of graphs, especially for stars, paths and cycles.

2. Stars, Paths and Cycles

As all graphs are (super) EAT, see Proposition 1, and all graphs are (super) VAT, see Proposition 2, we trivially get, that a graph that is simultaneously VMT and EAT, must be VMT. Analogously, the necessary condition for a graph to be simultaneously VAT and EMT is that the graph must be EMT.

The star $S_{n}$ is a graph isomorphic to the complete bipartite graph $K_{1, n}$ . In [9] it was proved that the star $S_{n}$ is totally magic if and only if $n = 2$ . Bača, Miller, Phanalasy, Ryan, Semaničová-Feňovčíková and Sillasen in [8] proved that the star $S_{n}$ is TAT for $n \geq 1$ .

Kotzig and Rosa [1] proved that the complete bipartite graph $K_{m, n}$ is EMT for all integers $m$ , $n$ . Immediately from this result we get that all stars $S_{n}$ are EMT. We now prove the following result.

Theorem 1. The star $S_{n}$ is simultaneously EMT and VAT if and only if $n = 1$ .

Proof. We denote the vertices of $S_{n}$ by the symbols $v$ , $v_{i}$ , $i = 1, 2, \dots, n$ , such that $E (S_{n}) = {v v_{1}, v v_{2}, \dots, v v_{n}} .$

Let $f$ be a total labeling of $S_{n}$ that is simultaneously EMT and VAT. It means that the edges $v v_{1}$ and $v v_{i}$ , $i = 2, 3, \dots, n$ , have the same weights, i.e., $\begin{aligned} w t_{f} (v v_{1}) = & w t_{f} (v v_{i}) \\ f (v) + f (v v_{1}) + f (v_{1}) = & f (v) + f (v v_{i}) + f (v_{i}) \\ f (v_{1}) + f (v v_{1}) = & f (v v_{i}) + f (v_{i}) \\ w t_{f} (v_{1}) = & w t_{f} (v_{i}) . \end{aligned}$ The labeling $f$ must be also a VAT labeling of $S_{n}$ , thus the vertex-weights must be pairwise different. But this is possible if and only if $n = 1$ .

In [2] it was proved that the complete bipartite graph $K_{m, n}$ is VMT if and only if $| m - n | \leq 1$ . Note that $S_{1}$ is isomorphic to a path on 2 vertices and $S_{2}$ is isomorphic to a path on 3 vertices. In [2] MacDougall, Miller, Slamin and Wallis proved that the path on $n$ vertices is VMT for $n > 2$ . According to these facts the star $S_{n}$ is VMT if and only if $n = 2$ .

Theorem 2. No star $S_{n}$ is simultaneously VMT and EAT.

Proof. We only need to show that the star $S_{2}$ in not simultaneously VMT and EAT. It is easy to check that there are only two non-isomorphic VMT labelings of $P_{3}$ , both are illustrated in Figure 1. But both of these labelings are simultaneously EMT.

Figure 1: The Only Two Non-Isomorphic VMT Labelings of Star $P_{3}$ . Both Are Simultaneously EMT

MacDougall, Miller, Slamin and Wallis [2] proved that the path $P_{n}$ on $n$ vertices and a cycle $C_{n}$ are VMT for $n \geq 3$ . In [9] it was proved that $P_{n}$ is totally magic if and only if $n = 3$ . Bača, Miller, Phanalasy, Ryan, Semaničová-Feňovčíková and Sillasen in [8] proved that $P_{n}$ is TAT for every $n \geq 2$ .

Theorem 3. The path $P_{n}$ is simultaneously EMT and VAT if and only if $n \neq 3$ .

Proof. We denote the vertices of $P_{n}$ by the symbols $v_{i}$ , $i = 1, 2, \dots, n$ , such that $E (P_{n}) = {v_{1} v_{2}, v_{2} v_{3}, \dots, v_{n - 1} v_{n}} .$

First we prove that the path $P_{3}$ is not simultaneously EMT and VAT. We prove it by contradiction. Let us consider that $g$ is a labeling of $P_{3}$ that is simultaneously EMT and VAT. It means that the edges $v_{1} v_{2}$ and $v_{2} v_{3}$ have the same weights, i.e., $\begin{aligned} w t_{g} (v_{1} v_{2}) = & w t_{g} (v_{2} v_{3}) \\ g (v_{1}) + g (v_{1} v_{2}) + g (v_{2}) = & g (v_{2}) + g (v_{2} v_{3}) + g (v_{3}) \\ g (v_{1}) + g (v_{1} v_{2}) = & g (v_{2} v_{3}) + g (v_{3}) \\ w t_{g} (v_{1}) = & w t_{g} (v_{3}) . \end{aligned}$ But this is a contradiction to the fact that $g$ is a VAT labeling of $P_{3}$ .

For $n \neq 3$ , let us consider the labeling $f$ , $f : V (P_{n}) \cup E (P_{n}) \to {1, 2, \dots, 2 n - 1}$ defined in the following way $\begin{aligned} f (v_{i}) & = {\begin{cases} \frac{i}{2}, & i \equiv 0 (\mod 2), i \leq n, \\ ⌊ \frac{n}{2} ⌋ + \frac{i + 1}{2}, & i \equiv 1 (\mod 2), i \leq n, \end{cases} \\ f (v_{i} v_{i + 1}) & = 2 n - i, i = 1, 2, 3, \dots, n - 1. \end{aligned}$

For the edge-weights we have the following.
If $i \equiv 0 (\mod 2)$ , $2 \leq i \leq n - 1$ then $\begin{aligned} w t_{f} (v_{i} v_{i + 1}) = & f (v_{i}) + f (v_{i} v_{i + 1}) + f (v_{i + 1}) \\ = & (\frac{i}{2}) + (2 n - i) + (⌊ \frac{n}{2} ⌋ + \frac{(i + 1) + 1}{2}) = 2 n + ⌊ \frac{n}{2} ⌋ + 1. \end{aligned}$ If $i \equiv 1 (\mod 2)$ , $1 \leq i \leq n - 1$ then $\begin{aligned} w t_{f} (v_{i} v_{i + 1}) = & f (v_{i}) + f (v_{i} v_{i + 1}) + f (v_{i + 1}) \\ = & (⌊ \frac{n}{2} ⌋ + \frac{i + 1}{2}) + (2 n - i) + (\frac{i + 1}{2}) = 2 n + ⌊ \frac{n}{2} ⌋ + 1. \end{aligned}$ Thus the labeling $f$ is EMT.

Let us consider the vertex-weights under the labeling $f$ . $\begin{aligned} w t_{f} (v_{1}) = & f (v_{1}) + f (v_{1} v_{2}) = (⌊ \frac{n}{2} ⌋ + \frac{1 + 1}{2}) + (2 n - 1) = 2 n + ⌊ \frac{n}{2} ⌋, \\ w t_{f} (v_{n}) = & f (v_{n}) + f (v_{n - 1} v_{n}) \\ = & {\begin{cases} \frac{n}{2} + (2 n - (n - 1)) = \frac{3 n}{2} + 1, \\ for n \equiv 0 (\mod 2), \\ (⌊ \frac{n}{2} ⌋ + \frac{n + 1}{2}) + (2 n - (n - 1)) = 2 n + 1, \\ for n \equiv 1 (\mod 2), \end{cases} \\ w t_{f} (v_{i}) = & f (v_{i - 1} v_{i}) + f (v_{i}) + f (v_{i} v_{i + 1}) \\ = & {\begin{cases} (2 n - (i - 1)) + \frac{i}{2} + (2 n - i) = 4 n + 1 - \frac{3 i}{2}, \\ for i \equiv 0 (\mod 2), 2 \leq i < n \\ (2 n - (i - 1)) + (⌊ \frac{n}{2} ⌋ + \frac{i + 1}{2}) + (2 n - i) \\ = 4 n + ⌊ \frac{n}{2} ⌋ - \frac{3 (i - 1)}{2}, \\ for i \equiv 1 (\mod 2), 3 \leq i < n . \end{cases} \end{aligned}$ It is easy to see that the following is true:

For $n \neq 3$ , we have $w t_{f} (v_{n}) < w t_{f} (v_{1})$ .
For every positive integer $i$ , $2 \leq i \leq n - 1$ it holds that $w t_{f} (v_{1}) < w t_{f} (v_{i}) .$
To prove that $f$ is a VAT labeling of $P_{n}$ we need to show that for all positive integers $i$ , $j$ , $1 < i, j < n$ we have $\begin{matrix} (1) & w t_{f} (v_{i}) \neq w t_{f} (v_{j}) . \end{matrix}$

If $i \equiv j (\mod 2)$ then the proof is trivial, as in this case the vertex-weights form an arithmetic sequence with difference 3.

If $i ≢ j (\mod 2)$ then the inequality (1) is true for $⌊ \frac{n}{2} ⌋ ≢ 1 (\mod 3)$ .

Thus the labeling $f$ is a simultaneously EMT and VAT labeling of $P_{n}$ for $n \neq 3$ and $n ≢ 2 (\mod 6)$ and $n ≢ 3 (\mod 6)$ .

For $n \equiv 2 (\mod 6)$ let us consider the labeling $h$ of $P_{n}$ defined by $\begin{aligned} h (v_{i}) & = {\begin{cases} \frac{n + i}{2}, & i \equiv 0 (\mod 2), i \leq n, \\ \frac{i + 1}{2}, & i \equiv 1 (\mod 2), i \leq n - 1, \end{cases} \\ h (v_{i} v_{i + 1}) & = 2 n - i, i = 1, 2, 3, \dots, n - 1. \end{aligned}$

For the edge-weights under the labeling $h$ we get:
If $i \equiv 0 (\mod 2)$ , $2 \leq i \leq n - 2$ then $\begin{aligned} w t_{h} (v_{i} v_{i + 1}) = & h (v_{i}) + h (v_{i} v_{i + 1}) + h (v_{i + 1}) \\ = & (\frac{n + i}{2}) + (2 n - i) + (\frac{(i + 1) + 1}{2}) = \frac{5 n}{2} + 1. \end{aligned}$ If $i \equiv 1 (\mod 2)$ , $1 \leq i \leq n - 1$ then $\begin{aligned} w t_{h} (v_{i} v_{i + 1}) = & h (v_{i}) + h (v_{i} v_{i + 1}) + h (v_{i + 1}) \\ = & (\frac{i + 1}{2}) + (2 n - i) + (\frac{n + (i + 1)}{2}) = \frac{5 n}{2} + 1. \end{aligned}$ Thus the labeling $h$ is EMT.

For the vertex-weights under the labeling $h$ we have: $\begin{aligned} w t_{h} (v_{1}) = & h (v_{1}) + h (v_{1} v_{2}) = (\frac{1 + 1}{2}) + (2 n - 1) = 2 n, \\ w t_{h} (v_{n}) = & h (v_{n}) + h (v_{n - 1} v_{n}) = (\frac{n + n}{2}) + (2 n - (n - 1)) = 2 n + 1, \\ w t_{h} (v_{i}) = & h (v_{i - 1} v_{i}) + h (v_{i}) + h (v_{i} v_{i + 1}) \\ = & {\begin{cases} (2 n - (i - 1)) + \frac{n + i}{2} + (2 n - i) = \frac{9 n}{2} + 1 - \frac{3 i}{2}, \\ for i \equiv 0 (\mod 2), 2 \leq i \leq n - 2, \\ (2 n - (i - 1)) + (\frac{i + 1}{2}) + (2 n - i) = 4 n - \frac{3 (i - 1)}{2}, \\ for i \equiv 1 (\mod 2), 3 \leq i \leq n - 1. \end{cases} \end{aligned}$

Then we get:

For every positive integer $i$ , $2 \leq i \leq n - 1$ it holds that $w t_{h} (v_{1}) = 2 n < 2 n + 1 = w t_{h} (v_{n}) < w t_{h} (v_{i}) .$
To prove that $h$ is a VAT labeling of $P_{n}$ we need to show that for all positive integers $i$ , $j$ , $1 < i, j < n$ we have $\begin{matrix} (2) & \begin{aligned} w t_{h} (v_{i}) \neq w t_{h} (v_{j}) . \end{aligned} \end{matrix}$

If $i \equiv j (\mod 2)$ then the proof is again trivial, as the vertex-weights form an arithmetic sequence with difference 3.

If $i ≢ j (\mod 2)$ then the inequality (2) is true for $n ≢ 4 (\mod 6)$ . However, this condition is satisfied as we considered the case when $n \equiv 2 (\mod 6)$ .

It means that for $n \equiv 2 (\mod 6)$ the labeling $h$ is a simultaneously EMT and VAT labeling of $P_{n}$ .

For $n \equiv 3 (\mod 6)$ , $n \geq 9$ , let us consider the labeling $t$ of $P_{n}$ defined in the following way: $\begin{aligned} t (v_{i}) & = {\begin{cases} \frac{3 n - 1}{2} + \frac{i}{2}, & i \equiv 0 (\mod 2), i \leq n - 1, \\ \frac{i + 1}{2}, & i \equiv 1 (\mod 2), i \leq n, \end{cases} \\ t (v_{i} v_{i + 1}) & = \frac{3 n + 1}{2} - i, i = 1, 2, 3, \dots, n - 1. \end{aligned}$

Analogously as in the previous cases we can prove that $t$ is simultaneously EMT and VAT labeling of $P_{n}$ for $n \equiv 3 (\mod 6)$ .

In Figures 2, 3 and 4 we illustrate simultaneously EMT and VAT labelings of $P_{7}$ , $P_{8}$ and $P_{9}$ , respectively.

Theorem 4. For $n = 4$ or $n \geq 5$ , $n \equiv 1 (\mod 6)$ or $n \equiv 5 (\mod 6)$ the path $P_{n}$ is simultaneously VMT and EAT.

Proof. Figure 5 shows a labeling of $P_{4}$ that is simultaneously VMT and EAT.

Figure 5: Simultaneously VMT and EAT Labeling of $P_{4}$

Let $n$ be a positive integer, $n \geq 5$ , $n \equiv 1 (\mod 6)$ or $n \equiv 5 (\mod 6)$ . Let us consider the labeling $f$ , $f : V (P_{n}) \cup E (P_{n}) \to {1, 2, \dots, 2 n - 1}$ defined in the following way: $\begin{aligned} f (v_{i}) & = {\begin{cases} 2 n - 1, & i = n, \\ 2 n - 1 - i, & i = 1, 2, \dots, n - 1, \end{cases} \\ f (v_{i} v_{i + 1}) & = {\begin{cases} \frac{i}{2}, & i \equiv 0 (\mod 2), i \leq n - 1, \\ \frac{n + i}{2}, & i \equiv 1 (\mod 2), i \leq n - 2. \end{cases} \end{aligned}$

For the vertex-weights under the labeling $f$ we get: $\begin{aligned} w t_{f} (v_{1}) = & f (v_{1}) + f (v_{1} v_{2}) = (\frac{n + 1}{2}) + (2 n - 2) = \frac{5 n - 3}{2}, \\ w t_{f} (v_{n}) = & f (v_{n}) + f (v_{n - 1} v_{n}) = (2 n - 1) + (\frac{n - 1}{2}) = \frac{5 n - 3}{2}, \\ w t_{f} (v_{i}) = & f (v_{i - 1} v_{i}) + f (v_{i}) + f (v_{i} v_{i + 1}) \\ = & {\begin{cases} (\frac{n + (i - 1)}{2}) + (2 n - 1 - i) + (\frac{i}{2}) = \frac{5 n - 3}{2}, \\ for i \equiv 0 (\mod 2), 2 \leq i \leq n - 1, \\ (\frac{i - 1}{2}) + (2 n - 1 - i) + (\frac{n + i}{2}) = \frac{5 n - 3}{2}, \\ for i \equiv 1 (\mod 2), 3 \leq i \leq n - 2. \end{cases} \end{aligned}$ Thus for $i = 1, 2, \dots, n$ we have $w t_{f} (v_{i}) = \frac{5 n - 3}{2}$ . This means that the labeling $f$ is VMT.

Let us consider the edge-weights under the labeling $f$ . If $i \equiv 0 (\mod 2)$ , $2 \leq i \leq n - 3$ then $\begin{aligned} w t_{f} (v_{i} v_{i + 1}) = & f (v_{i}) + f (v_{i} v_{i + 1}) + f (v_{i + 1}) \\ = & (2 n - 1 - i) + (\frac{i}{2}) + (2 n - 1 - (i + 1)) = 4 n - 3 - \frac{3 i}{2} . \end{aligned}$ Thus the set of edge-weights for $i$ even is ${w t_{f} (v_{2} v_{3}), w t_{f} (v_{4} v_{5}), \dots, w t_{f} (v_{n - 3} v_{n - 2})} = {4 n - 6, 4 n - 9, \dots, \frac{5 n + 3}{2}} .$ The edge-weights form an arithmetic sequence with a difference 3. For $n \equiv 1 (\mod 6)$ the numbers in the set of edge-weights are congruent to 1 modulo 3. For $n \equiv 5 (\mod 6)$ the numbers that form the set of edge-weights are congruent to 2 modulo 3.

If $i \equiv 1 (\mod 2)$ , $1 \leq i \leq n - 2$ then $\begin{aligned} w t_{f} (v_{i} v_{i + 1}) = & f (v_{i}) + f (v_{i} v_{i + 1}) + f (v_{i + 1}) \\ = & (2 n - 1 - i) + (\frac{n + i}{2}) + (2 n - 1 - (i + 1)) = \frac{9 n - 3 i}{2} - 3. \end{aligned}$ The set of edge-weights for $i$ odd form an arithmetic sequence with difference 3, more precisely ${w t_{f} (v_{1} v_{2}), w t_{f} (v_{3} v_{4}), \dots, w t_{f} (v_{n - 2} v_{n - 1})} = {\frac{9 n - 9}{2}, \frac{9 n - 9}{2} - 3, \dots, 3 n} .$ Moreover, in this case the edge-weights are congruent to 0 modulo 3.

And $\begin{aligned} w t_{f} (v_{n - 1} v_{n}) = & f (v_{n - 1}) + f (v_{n - 1} v_{n}) + f (v_{n}) \\ = & (2 n - 1 - (n - 1)) + (\frac{n - 1}{2}) + (2 n - 1) = \frac{7 n - 3}{2} \\ \equiv & {\begin{cases} 2 (\mod 3), for n \equiv 1 (\mod 6), \\ 1 (\mod 3), for n \equiv 5 (\mod 6) . \end{cases} \end{aligned}$

According to the previous discussions for $n \geq 5$ , $n \equiv 1 (\mod 6)$ or $n \equiv 5 (\mod 6)$ edge-weights are pairwise different.

Thus the labeling $f$ is a simultaneously VMT and EAT labeling of $P_{n}$ for $n \geq 5$ , $n \equiv 1 (\mod 6)$ or $n \equiv 5 (\mod 6)$ .

Note that $P_{2}$ and $P_{3}$ are not simultaneously VMT and EAT. For $6 \leq n ≢ 1, 5 (\mod 6)$ we are not able to find the corresponding total labeling that is simultaneously VMT and EAT. However we assume that such a labeling does exist. The supporting argument for this assumption is the fact that every VMT labeling of path $P_{n}$ is derived from VMT labeling of cycle $C_{n}$ , see [2]. And for cycles there exist many non-isomorphic VMT labelings, see Table 1 [2].

Table 1: Number of Non-Isomorphic VMT Labelings of Cycle $C_{n}$ [2]
$n$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
$#$	$4$	$6$	$6$	$20$	$118$	$282$	$1540$	$7092$

In [9] it was proved that the cycle $C_{n}$ is totally magic if and only if $n = 3$ . Bača, Miller, Phanalasy, Ryan, Semaničová-Feňovčíková and Sillasen in [8] proved that all cycles $C_{n}$ are TAT.

We now prove the following result.

Theorem 5. For $n = 4$ or $n \geq 5$ , $n \equiv 1 (\mod 6)$ or $n \equiv 5 (\mod 6)$ the cycle $C_{n}$ is simultaneously VMT and EAT.

Proof. As we already mentioned, every VMT labeling of path $P_{n}$ is derived from VMT labeling of cycle $C_{n}$ , see [2]. The idea is to modify the VMT labeling of cycle $C_{n}$ by subtracting number 1 from every vertex label and every edge label of a VMT labeling of the cycle $C_{n}$ and then to delete the edge with label 0.

Thus, according to the proof of Theorem 4, let us consider the labeling $f$ , $f : V (C_{n}) \cup E (C_{n}) \to {1, 2, \dots, 2 n}$ defined in the following way: $\begin{aligned} f (v_{i}) & = {\begin{cases} 2 n, & i = n, \\ 2 n - i, & i = 1, 2, \dots, n - 1, \end{cases} \\ f (v_{i} v_{i + 1}) & = {\begin{cases} \frac{i}{2} + 1, & i \equiv 0 (\mod 2), i \leq n - 1, \\ \frac{n + i}{2} + 1, & i \equiv 1 (\mod 2), i \leq n - 2, \end{cases} \\ f (v_{1} v_{n}) & = 1. \end{aligned}$

Analogously as in the proof of Theorem 4 we prove that the labeling $f$ is a simultaneously VMT and EAT labeling of $C_{n}$ for $n \geq 5$ , $n \equiv 1 (\mod 6)$ or $n \equiv 5 (\mod 6)$ .

According to Theorem 5 and the fact that for cycles (and only for cycles) a VMT labeling is equivalent to EMT labeling, see [3], we have:

Theorem 6. For $n = 4$ or $n \geq 5$ , $n \equiv 1 (\mod 6)$ or $n \equiv 5 (\mod 6)$ the cycle $C_{n}$ is simultaneously EMT and VAT.

Note that for the cycle $C_{3}$ there is neither a simultaneously VMT and EAT labeling nor a simultaneously EMT and VAT labeling. The cases when $6 \leq n ≢ 1, 5 (\mod 6)$ are still unsolved.

3. Conclusion

In this paper we have dealt with the problem of finding a total labeling of some classes of graphs that is simultaneously vertex-magic and edge-antimagic or simultaneously vertex-antimagic and edge-magic, respectively. We showed the existence of such labelings for some classes of graphs, such as stars, paths and cycles.

For $n = 4$ or $n \geq 5$ , $n \equiv 1 (\mod 6)$ or $n \equiv 5 (\mod 6)$ we proved that the cycle $C_{n}$ is simultaneously EMT and VAT. For other cases we propose the following open problem.

Problem 3. For the cycle $C_{n}$ , $6 \leq n ≢ 1, 5 (\mod 6)$ , determine if there is a simultaneously EMT labeling and VAT labeling.

For further investigation we state the following open problem.

Problem 4. Find other classes of graphs that are simultaneously VMT and EAT or simultaneously VAT and EMT, respectively.

Acknowledgment

The work was supported by the Slovak Research and Development Agency under the contract No. APVV-19-0153.

References:

Kotzig, A. and Rosa, A., 1970. Magic valuations of finite graphs. Canadian Mathematical Bulletin, 13(4), pp.451-461.
MacDougall, J.A., Miller, M., Slamin and Wallis, W.D., 2002. Vertex-magic total labelings of graphs. Utilitas Mathematica, 61, pp.3-21.
Wallis, W. D., 2001. Magic Graphs, Birkhäuser, Boston – Basel – Berlin.
Simanjuntak, R., Bertault, F. and Miller, M., 2000. Two new $(a, d)$ -antimagic graph labelings. In Proc. of Eleventh Australasian Workshop on Combinatorial Algorithms (Vol. 11, pp. 179-189).
Bača, M., MacDougall, J., Bertault, F., Miller, M., Simanjuntak, R. and Slamin, 2003. Vertex-antimagic total labelings of graphs. Discussiones Mathematicae Graph Theory, 23(1), pp.67-83.
Bača, M. and Miller, M., 2008. Super Edge-Antimagic Graphs: A Wealth of Problems and Some Solutions. Universal-Publishers.
Miller, M., Phanalasy, O. and Ryan, J., 2011. All graphs have antimagic total labelings. Electronic Notes in Discrete Mathematics, 38, pp.645-650.
Bača, M., Miller, M., Phanalasy, O., Ryan, J., Semaničová-Feňovčíková, A. and Sillasen, A.A., 2015. Totally antimagic total graphs. The Australasian Journal of Combinatorics, 61, pp.42-56.
Exoo, G., Ling, A.C., McSorley, J.P., Phillips, N.C. and Wallis, W.D., 2002. Totally magic graphs. Discrete Mathematics, 254(1-3), pp.103-113.

[1] Kotzig, A. and Rosa, A., 1970. Magic valuations of finite graphs. Canadian Mathematical Bulletin, 13(4), pp.451-461.

[2] MacDougall, J.A., Miller, M., Slamin and Wallis, W.D., 2002. Vertex-magic total labelings of graphs. Utilitas Mathematica, 61, pp.3-21.

[3] Wallis, W. D., 2001. Magic Graphs, Birkhäuser, Boston – Basel – Berlin.

[4] Simanjuntak, R., Bertault, F. and Miller, M., 2000. Two new $(a, d)$ -antimagic graph labelings. In Proc. of Eleventh Australasian Workshop on Combinatorial Algorithms (Vol. 11, pp. 179-189).

[5] Bača, M., MacDougall, J., Bertault, F., Miller, M., Simanjuntak, R. and Slamin, 2003. Vertex-antimagic total labelings of graphs. Discussiones Mathematicae Graph Theory, 23(1), pp.67-83.

[6] Bača, M. and Miller, M., 2008. Super Edge-Antimagic Graphs: A Wealth of Problems and Some Solutions. Universal-Publishers.

[7] Miller, M., Phanalasy, O. and Ryan, J., 2011. All graphs have antimagic total labelings. Electronic Notes in Discrete Mathematics, 38, pp.645-650.

[8] Bača, M., Miller, M., Phanalasy, O., Ryan, J., Semaničová-Feňovčíková, A. and Sillasen, A.A., 2015. Totally antimagic total graphs. The Australasian Journal of Combinatorics, 61, pp.42-56.

[9] Exoo, G., Ling, A.C., McSorley, J.P., Phillips, N.C. and Wallis, W.D., 2002. Totally magic graphs. Discrete Mathematics, 254(1-3), pp.103-113.

Contents

Journal of Combinatorial Mathematics and Combinatorial Computing

Total Labelings of Graphs with Prescribed Weights

Abstract

1. Introduction

2. Stars, Paths and Cycles

3. Conclusion

Acknowledgment

References:

Information

Guidelines

CP Initiatives

Follow CP