Yu Bin Tai, Gek L. Chia^∗ , Poh-Hwa Ong

Department of Mathematical and Actuarial Sciences, Lee Kong Chian Faculty of Engineering and Science, Unversiti Tunku Abdul Rahman, Sungai Long Campus, Malaysia

shotztai@1utar.my, chiagl@utar.edu.my, ongph@utar.edu.my

^∗Corresponding author

An anti-magic graph is a graph whose |E| edges can be labeled with the first |E| natural numbers such that each edge receives a distinct number and each vertex receives a distinct vertex sum which is obtained by taking the sum of the labels of all the edges incident to it. We prove that the multibridge graph is anti-magic.

Keywords: r-bridge graph, anti-magic labeling, anti-magic graph

Mathematics Subject Classification: 05C78

DOI: 10.5614/ejgta.2022.10.1.22

1. Introduction

Let G = (V, E) be a graph with neither loop nor multiple edges. An anti-magic labeling of G is a bijection ϕ from E to {1, 2, . . . , |E|} such that the sum of the labels on the edges incident to a vertex, called the vertex sum, is distinct for each vertex. A graph is anti-magic if it admits an anti-magic labeling.

The concept of anti-magic graphs has its origin from the book [7] where Hartsfield and Ringel conjectured that all connected graphs but the single edge K² are anti-magic. Since then, the problem of deciding which graphs are anti-magic has attracted much attention. Nevertheless the conjecture remains unsettled despite concerted efforts by mathematicians in graph theory.

Received: 2 June 2021, Revised: 7 April 2022, Accepted: 12 April 2022.

In the same book, Hartsfield and Ringel remarked that even when the conjecture is restricted to trees, no complete affirmative answer has been offered. Some results concerning the antimagicness of trees are given in [8] and [9].

On the other hand, by confining the attention on regular graphs, the situation turns out to be a lot more delightful. In [4], Cranston showed that every regular bipartite graph with degree at least 2 is anti-magic. In [5], Cranston et al. proved that Hartsfield and Ringel's conjecture is true for all odd regular graphs. Shortly afterwards, in [3], Chang et al. proved that all even regular graphs are anti-magic. By modifying the argument used in [5], Berczi et al. in [2] also proved that even ´ regular graphs are anti-magic. For more details on anti-magic graphs, we refer the reader to [6]. For some recent results on anti-magic graphs, we refer the reader to [10].

In view of this, we turn our attention to graphs which are close to being regular.

Consider a graph with only two vertices and having r multiple edges joining them, r ≥ 3. Subdivide the edges of this graph arbitrarily so that at most one edge is not subdivided. Call the result graph an r-bridge graph and denote it by θ(m1, m2, . . . , mr) if the lengths of the paths are m1, m2, . . . , m^r respectively.

The purpose of this paper is to prove the following result.

Theorem 1.1. Every r-bridge graph is anti-magic.

In a forth-coming paper, we shall make use of the above result to prove the anti-magicness of a class of not quite regular graphs. Hence it is an appetizer result for a more general result which is to appear later.

We note in passing that in [1], Alon et al. proved that all dense graphs are anti-magic while in [11], Wang initiated the investigation on the anti-magicness of sparse graphs. Incidentally, the graphs in this paper and those in our forth-coming papers are sparse graphs.

2. The proof of Theorem 1.1

Throughout this section, we shall assume that in the graph θ(m1, m2, . . . , mr), the path lengths satisfy the condition m¹ ≥ m² ≥ · · · ≥ mr. Also, we shall call the paths in θ(m1, m2, . . . , mr) the mi-path, i = 1, 2, . . . , r.

Let x and y denote the two vertices of degree r in θ(m1, m2, . . . , mr) and let w(x), w(y) denote the vertex sums of x, y respectively.

The proof is divided into three cases.

Case 1. r = 3k.

Suppose k = 1.

The labelings depicted in Figure 1 show that if m¹ ≤ 2, the 3-bridge graph is anti-magic. Hence we assume that m¹ ≥ 3.

Subcase 1.1. m¹ + m² + m³ is odd.

Let ϕ⁰ denote the following edge labeling on the 3-bridge graph.

• (i) Label the edges of the m1-path with 1, 2, . . . , m¹ successively starting from the vertex x.
• (ii) Label the edges of the m3-path with m¹ + 1, m¹ + 2, . . . , m¹ + m³ successively starting from the vertex y.

Figure 1. Anti-magic labelings where m¹ = 2.

(iii) Label the edges of the m2-path with m¹ + m³ + 1, m¹ + m³ + 2, . . . , m¹ + m³ + m² successively starting from the vertex x.

Figure 2(i) illustrates the case (m1, m2, m3) = (5, 4, 2).

Note that the vertex sums of the degree-2 vertices consist of distinct odd natural numbers and that the vertex sums of x and y are both even and are given by w(x) = 2(m¹ + m³ + 1) and w(y) = 2m¹ + m¹ + m² + m³ + 1 respectively.

This shows that ϕ⁰ is an anti-magic labeling of the 3-bridge graph.

Figure 2. Two anti-magic labelings on 3-bridges.

Subcase 1.2. m¹ + m² + m³ is even.

In this case, an anti-magic labeling is obtained by swapping the labels m¹ − 1, m¹ (on the last two edges of the m1-path) from the anti-magic labeling ϕ⁰ given in Subcase 1.1. Note that there are only three vertices whose vertex-sums are even, namely x, y and the second last vertex on the m1-path. Since the vertex-sums are 2(m1+m3+1), 2m1+m1+m2+m³ and 2m1−2 respectively, they are distinct natural numbers.

The vertex-sums of the rest of the vertices are distinct odd natural numbers.

Figure 2(ii) illustrates the case (m1, m2, m3) = (5, 4, 3).

Now suppose k ≥ 2.

For each i = 1, 2, . . . , k, let Hⁱ denote the 3-bridge subgraph induced by the m3i−2-path, m3i−1-path and the m3i-path.

Define p⁰ = 0 and pⁱ = pi−¹ + m3i−² + m3i−¹ + m3ⁱ for i ≥ 1.

For each i = 1, 2, . . . , k, label the edges of Hⁱ so that

• (i) the edges of the m3i−2-path receive the labels pi−1+1, pi−1+2, . . . , pi−1+m3i−² successively starting from the vertex x,
• (ii) and then label the edges of the m3i-path with pi−¹ +m3i−² +1, pi−¹ +m3i−² +2, . . . , pi−¹ + m3i−² + m3ⁱ successively starting from the vertex y.

(iii) Finally, label the edges of the \(m_{3i-1}\)-path with \(p_{i-1} + m_{3i-2} + m_{3i} + 1\), \(p_{i-1} + m_{3i-2} + m_{3i} + 2\), ..., \(p_{i-1} + m_{3i-2} + m_{3i} + m_{3i-1}\) starting from the vertex x.

Figure 3 illustrates the cases \((m_1, m_2, \dots, m_6) = (6, 6, 5, 4, 3, 2)\) and \((m_1, m_2, \dots, m_6) = (2, 2, \dots, 2)\).

Figure 3. Two anti-magic labelings on 6-bridges.

It is routine to check that the vertex sums of x and y are given by

\[w(x) = 2k + 2p_k - 2\sum_{i=1}^k m_{3i-1} + 3\sum_{i=1}^{k-1} p_i\]

and

\[w(y) = k + p_k + 2\sum_{i=1}^{k} m_{3i-2} + 3\sum_{i=1}^{k-1} p_i\]. respectively.

Also, note that the vertex sums of the degree-2 vertices consist of odd distinct natural numbers and are less than either of w(x) and w(y).

This completes the proof for Case 1.

Case 2. r = 3k + 1.

Suppose k = 1.

Subcase 2.1. Not all paths have the same length.

Let \(\varphi_1\) denote the following edge labeling on the 4-bridge graph.

• (i) Label the edges of the \(m_1\)-path with \(1, 2, \dots, m_1\) successively starting from the vertex x.
• (ii) Label the edges of the \(m_2\)-path with \(m_1 + 1, m_1 + 2, \dots, m_1 + m_2\) successively starting from the vertex x.
• (iii) Label the edges of the \(m_3\)-path with \(m_1 + m_2 + 1, m_1 + m_2 + 2, \dots, m_1 + m_2 + m_3\) successively starting from the vertex y.
• (iv) Label the edges of the \(m_4\)-path with \(m_1 + m_2 + m_3 + 1\), \(m_1 + m_2 + m_3 + 2\), ..., \(m_1 + m_2 + m_3 + m_4\) successively starting from the vertex y.

Figure 4(i) illustrates the case \((m_1, m_2, m_3, m_4) = (5, 4, 3, 2)\).

Note that the vertex sums w(x) and w(y) of x and y are given by \(3m_1 + 2m_2 + 2m_3 + m_4 + 2\) and \(4m_1 + 3m_2 + m_3 + 2\) respectively. Note that the vertex sums of the degree-2 vertices consist of distinct natural odd numbers and they are all less than either of w(x) and w(y).

This means that \(\varphi_1\) is an anti-magic labeling of the 4-bridge.

Figure 4. Two anti-magic labelings on 4-bridges.

Subcase 2.2. All paths have the same length m.

In this case, an anti-magic labeling is obtained by labeling the edges of the i-th path with the labels (i − 1)m + 1,(i − 1)m + 2, . . . , im successively all starting from x to y. In this case w(x) = 6m + 4 and w(y) = 10m. The rest of the vertex sums consist of distinct odd natural numbers.

Figure 4(ii) illustrates the case m = 3.

Figure 5. Two anti-magic labelings on 7-bridges.

Now suppose k ≥ 2.

Let H¹ denote the 4-bridge subgraph induced by the m^j -path, j = 1, 2, 3, 4. Also, for each i = 2, . . . , k, let Hⁱ denote the 3-bridge subgraph induced by the m3i−1-path, m3i-path and the m3i+1-path.

Define p⁰ = 0 , p¹ = m¹ + m² + m³ + m⁴ and pⁱ = pi−¹ + m3i−¹ + m3ⁱ + m3i+1 for i ≥ 2. Label H¹ using ϕ¹ first. Then for each i = 2, . . . , k, label the edges of Hⁱ so that

• (i) the edges of the m3i−1-path receive the labels pi−1+1, pi−1+2, . . . , pi−1+m3i−¹ successively starting from the vertex x, and
• (ii) label the edges of the m3i+1-path with pi−¹ + m3i−¹ + 1, pi−¹ + m3i−¹ + 2, . . . , pi−¹ + m3i−¹ + m3i+1 successively starting from the vertex y.
• (iii) Finally, label the edges of the m3i-path with pi−¹ + m3i−¹ + m3i+1 + 1, pi−¹ + m3i−¹ + m3i+1 + 2, . . . , pi−¹ + m3i−¹ + m3i+1 + m3ⁱ starting from the vertex x.

Figure 5 illustrates the cases (m1, m2, . . . , m7) = (6, 5, 4, 3, 3, 3, 2) and (m1, m2, . . . , m7) = (2, 2, . . . , 2).

It is routine to check that the vertex sums of x and y are given by

\[w(x) = 2p_k + 2k + m_1 - m_4 + \sum_{i=2}^{k} (3p_{i-1} - 2m_{3i})\]

and

\[w(y) = k+1+4m_1+3m_2+m_3+2(p_1-p_k)+\sum_{i=2}^k (3p_i+2m_{3i-1})\] . respectively.

Also, note that the vertex sums of the degree-2 vertices consist of distinct odd natural numbers each of which is less than either of w(x) and w(y).

This completes the proof for Case 2.

Case 3. r = 3k + 2.

Suppose k = 1.

Let ϕ² denote the following edge labeling on the 5-bridge graph.

• (i) Label the edges of the m1-path with 1, 2, . . . , m¹ successively starting from the vertex x.
• (ii) Label the edges of the m2-path with m¹ + 1, m¹ + 2, . . . , m¹ + m² successively starting from the vertex y.
• (iii) For each i ∈ {3, 4, 5}, label the edges of the mi-path with qⁱ + 1, qⁱ + 2, . . . , qⁱ + mⁱ successively all starting from x to y. Here q³ = m¹ + m² and q^j = qj−¹ + mj−¹ for j ∈ {4, 5}.

Figure 6 illustrates the case (m1, m2, m3, m4, m5) = (6, 5, 4, 3, 2).

Figure 6. Anti-magic labeling of a 5-bridge.

Note that the vertex sums of x and y are given by w(x) = 4(m¹ + m2) + 2m³ + m⁴ + 4 and w(y) = 5m¹ + 3(m² + m3) + 2m⁴ + m⁵ + 1 respectively.

Clearly the vertex sums of the degree-2 vertices in ϕ² consist of odd distinct natural numbers and each is less than either of w(x) and w(y).

Hence ϕ² is an anti-magic labeling of the 5-bridge.

Now suppose k ≥ 2.

Let H¹ denote the 5-bridge induced by the m^j -path, j = 1, 2, . . . , 5. Also, for each i = 2, . . . , k, let Hⁱ denote the 3-bridge subgraph induced by the m3i-path, m3i+1-path and the m3i+2 path.

Define p⁰ = 0 , p¹ = m¹ + m² + · · · + m⁵ and pⁱ = pi−¹ + m3ⁱ + m3i+1 + m3i+2 for i ≥ 2.

Label H¹ using ϕ² first. Then for each i = 2, . . . , k, label the edges of Hⁱ so that

(i) the edges of the m3i-path receive the labels pi−¹ + 1, pi−¹ + 2, . . . , pi−¹ + m3ⁱ successively starting from the vertex x, and

• (ii) label the edges of the m3i+2-path with pi−1+m3i+1, pi−1+m3i+2, . . . , pi−1+m3i+m3i+2 successively starting from the vertex y.
• (iii) Finally, label the edges of the m3i+1-path with pi−1+m3i+m3i+2+1, pi−1+m3i+m3i+2+ 2, . . . , pi−¹ + m3ⁱ + m3i+2 + m3i+1 starting from the vertex x.

Figure 7 illustrates the case (m1, m2, . . . , m8) = (6, 5, 4, 3, 3, 3, 2, 2).

Figure 7. Anti-magic labeling of an 8-bridge.

It is routine to check that the vertex sums of x and y are given by

\[w(x) = 2(p_k + k + 1 + m_1 + m_2 - m_5) - m_4 + \sum_{i=2}^{k} (3p_{i-1} - 2m_{3i+1})\] and

\[w(y) = 2(2m_1 + m_2 + m_3) + m_4 + k + p_k + \sum_{i=2}^{k} (3p_{i-1} + 2m_{3i})\] respectively.

Also, note that the vertex sums of the degree-2 vertices consist of distinct odd natural numbers each of which is less than either of w(x) and w(y).

This completes the proof for Case 3 and so is the proof for Theorem 1.1.

Acknowledgement

The research was supported by the Ministry of Higher Education (MoHE) through Fundamental Research Grant Scheme project FRGS/1/2018/STG06/UTAR/01/1.

References

• [1] N. Alon, G. Kaplan, A. Lev, Y. Roditty, and R. Yuster, Dense graphs are antimagic, J. Graph Theory 47 (2004) 297–309.
• [2] K. Berczi, A. Bern ´ ath, and M. Vizer, Regular graphs are antimagic, ´ Electron. J. Combin., 22 (2015) P3.34.
• [3] F. Chang, Y.C. Liang, Z. Pan, and X. Zhu, Antimagic labeling of regular graphs, J. Graph Theory 82 (2016) 339–349.

• [4] D.W. Cranston, Regular bipartite graphs are antimagic, J. Graph Theory, 60 (2009) 173–182.
• [5] D.W. Cranston, Y.C. Liang, and X. Zhu, Regular graphs of odd degree are anti-magic, J. Graph Theory, 80 (2015) 28–33.
• [6] J.A. Gallian, A dynamic survey on graph labelings, Electron. J. Combin., (Dec 2021) # DS6.
• [7] N. Hartsfield and G. Ringel, Pearls in Graph Theory, Academic Press, Boston, (1990) 108– 109.
• [8] G. Kaplan, A. Lev, and Y. Roditty, On zero-sum partitions and anti-magic trees, Discrete Math., 309 (2009) 2010–2014.
• [9] Y.C. Liang, T.L. Wong, and X. Zhu, Anti-magic labeling of trees, Discrete Math., 331 (2014) 9–14.
• [10] R. Simanjuntak, T. Nadeak, F. Yasin, K. Wijaya, N. Hinding, and K.A. Sugeng, Another Antimagic Conjecture, Symmetry, 13 (2021) 2071. https : //doi.org/10.3390/sym13112071
• [11] T. Wang, Toroidal grids are anti-magic, Lecture Notes in Comput. Sci., 3595 (2005) 671–679.