Article in volume
Authors:
Title:
Antimagic labeling of some biregular bipartite graphs
PDFSource:
Discussiones Mathematicae Graph Theory 42(4) (2022) 1205-1218
Received: 2019-08-12 , Revised: 2020-06-01 , Accepted: 2020-06-01 , Available online: 2020-06-24 , https://doi.org/10.7151/dmgt.2340
Abstract:
An antimagic labeling of a graph $G=(V,E)$ is a one-to-one mapping from $E$ to
$\{1, 2, \dots, |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
$K_2$ 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\geq3$) bipartite graph is
antimagic; (2) Each $(k,pk)$-biregular ($k\geq3,p\geq2$) bipartite graph is
antimagic; (3) Each $(k,k^2+y)$-biregular ($k\geq3,y\geq1$) bipartite graph is
antimagic.
Keywords:
antimagic labeling, bipartite, biregular
References:
- 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 - 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 - D.W. Cranston, Regular bipartite graphs are antimagic, J. Graph Theory 60 (2009) 173–182.
https://doi.org/10.1002/jgt.20347 - 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 - 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 - T. Eccles, Graphs of large linear size are antimagic, J. Graph Theory 81 (2016) 236–261.
https://doi.org/10.1002/jgt.21872 - J.A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. (2018) #DS6.
https://doi.org/10.37236/27 - N. Hartsfield and G. Ringel, Super magic and antimagic graphs, J. Recreat. Math. 21 (1989) 107–115.
- N. Hartsfield and G. Ringel, Pearls in Graph Theory (Academic Press, INC, Boston, 1990).
- 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 - 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 - 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 - 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 - A. Lozano, M. Mora, C. Seara and J. Tey, Caterpillars are antimagic.
arXiv: 1812.06715v2 - V. Longani, Extension of Hall's theorem and an algorithm for finding the $(1,n)$-complete matching, Thai J. Math. 6 (2008) 271–277.
- L. Mirsky, Transversal Theory (Academic Press, New York, 1971).
- J.L. Shang, Spiders are antimagic, Ars Combin. 118 (2015) 367–372.
Close