1. bookVolume 42 (2022): Issue 4 (November 2022)
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

Antimagic Labeling of Some Biregular Bipartite Graphs

Published Online: 12 Jul 2022
Volume & Issue: Volume 42 (2022) - Issue 4 (November 2022)
Page range: 1205 - 1218
Received: 12 Aug 2019
Accepted: 01 Jun 2020
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

An antimagic labeling of a graph G = (V, E) is a one-to-one mapping from E to {1, 2, . . ., |E|} such that distinct vertices receive different label sums from the edges incident to them. G is called antimagic if it admits an antimagic labeling. It was conjectured that every connected graph other than K2 is antimagic. The conjecture remains open though it was verified for several classes of graphs such as regular graphs. A bipartite graph is called (k, k′)-biregular, if each vertex of one of its parts has the degree k, while each vertex of the other parts has the degree k′. This paper shows the following results. (1) Each connected (2, k)-biregular (k ≥ 3) bipartite graph is antimagic; (2) Each (k, pk)-biregular (k ≥ 3, p ≥ 2) bipartite graph is antimagic; (3) Each (k, k2 + y)-biregular (k ≥ 3, y ≥ 1) bipartite graph is antimagic.

Keywords

MSC 2010

[1] N. Alon, G. Kaplan, A. Lev, Y. Roditty and R. Yuster, Dense graphs are antimagic, J. Graph Theory 47 (2004) 297–309. https://doi.org/10.1002/jgt.20027 Search in Google Scholar

[2] F. Chang, Y.C. Liang, Z. Pan and X. Zhu, Antimagic labeling of regular graphs, J. Graph Theory 82 (2016) 339–349. https://doi.org/10.1002/jgt.21905 Search in Google Scholar

[3] D.W. Cranston, Regular bipartite graphs are antimagic, J. Graph Theory 60 (2009) 173–182. https://doi.org/10.1002/jgt.20347 Search in Google Scholar

[4] D.W. Cranston, Y.C. Liang and X. Zhu, Regular graphs of odd degree are antimagic, J. Graph Theory 80 (2015) 28–33. https://doi.org/10.1002/jgt.21836 Search in Google Scholar

[5] K.C. Deng and Y.F. Li, Caterpillars with maximum degree 3 are antimagic, Discrete Math. 342 (2019) 1799–1801. https://doi.org/10.1016/j.disc.2019.02.021 Search in Google Scholar

[6] T. Eccles, Graphs of large linear size are antimagic, J. Graph Theory 81 (2016) 236–261. https://doi.org/10.1002/jgt.21872 Search in Google Scholar

[7] J.A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. (2018) #DS6. https://doi.org/10.37236/27 Search in Google Scholar

[8] N. Hartsfield and G. Ringel, Super magic and antimagic graphs, J. Recreat. Math. 21 (1989) 107–115. Search in Google Scholar

[9] N. Hartsfield and G. Ringel, Pearls in Graph Theory (Academic Press, INC, Boston, 1990) 108–109. Search in Google Scholar

[10] G. Kaplan, A. Lev and Y. Roditty, On zero-sum partitions and anti-magic trees, Discrete Math. 309 (2009) 2010–2014. https://doi.org/10.1016/j.disc.2008.04.012 Search in Google Scholar

[11] Y.-C. Liang, T.-L. Wong and X. Zhu, Anti-magic labeling of trees, Discrete Math. 331 (2014) 9–14. https://doi.org/10.1016/j.disc.2014.04.021 Search in Google Scholar

[12] Y.-C. Liang and X. Zhu, Antimagic labeling of cubic graphs, J. Graph Theory 75 (2014) 31–36. https://doi.org/10.1002/jgt.21718 Search in Google Scholar

[13] A. Lozano, M. Mora and C. Seara, Antimagic labelings of caterpillars, Appl. Math. Comput. 347 (2019) 734–740. https://doi.org/10.1016/j.amc.2018.11.043 Search in Google Scholar

[14] A. Lozano, M. Mora, C. Seara and J. Tey, Caterpillars are antimagic. arXiv:1812.06715v2 Search in Google Scholar

[15] V. Longani, Extension of Hall’s theorem and an algorithm for finding the (1, n)-complete matching, Thai J. Math. 6 (2008) 271–277. Search in Google Scholar

[16] L. Mirsky, Transversal Theory (Academic Press, New York, 1971). Search in Google Scholar

[17] J.L. Shang, Spiders are antimagic, Ars Combin. 118 (2015) 367–372. Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo