×

Antimagic orientations of graphs with large maximum degree. (English) Zbl 1448.05178

Summary: Given a digraph \(D\) with \(m\) arcs, a bijection \(\tau:A(D)\to\{1,2,\ldots,m\}\) is an antimagic labeling of \(D\) if no two vertices in \(D\) have the same vertex-sum, where the vertex-sum of a vertex \(u\) in \(D\) under \(\tau\) is the sum of labels of all arcs entering \(u\) minus the sum of labels of all arcs leaving \(u\). We say \((D,\tau)\) is an antimagic orientation of a graph \(G\) if \(D\) is an orientation of \(G\) and \(\tau\) is an antimagic labeling of \(D\). Motivated by the conjecture of N. Hartsfield and G. Ringel [Pearls in graph theory. A comprehensive introduction. Boston etc.: Academic Press, Inc. (1990; Zbl 0703.05001) pp. 108–109] on antimagic labelings of graphs, D. Hefetz et al. [J. Graph Theory 64, No. 3, 219–232 (2010; Zbl 1209.05213)] initiated the study of antimagic orientations of graphs, and conjectured that every connected graph admits an antimagic orientation. This conjecture seems hard, and few related results are known. However, it has been verified to be true for regular graphs and biregular bipartite graphs. In this paper, we prove that every connected graph \(G\) on \(n\geq 9\) vertices with maximum degree at least \(n-5\) admits an antimagic orientation.

MSC:

05C78 Graph labelling (graceful graphs, bandwidth, etc.)
05C20 Directed graphs (digraphs), tournaments
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alon, N.; Kaplan, G.; Lev, A.; Roditty, Y.; Yuster, R., Dense graphs are antimagic, J. Graph Theory, 47, 297-309 (2004) · Zbl 1055.05132
[2] Bérczi, K.; Bernáth, A.; Vizer, M., Regular graphs are antimagic, Electron. J. Combin., 22 (2015), Paper 3.34 · Zbl 1323.05110
[3] Chang, F.; Liang, Y.-C.; Pan, Z.; Zhu, X., Antimagic labeling of regular graphs, J. Graph Theory, 82, 339-349 (2016) · Zbl 1372.05186
[4] Cranston, D., Regular bipartite graphs are antimagic, J. Graph Theory, 60, 173-182 (2009) · Zbl 1210.05141
[5] Cranston, D. W.; Liang, Y.-C.; Zhu, X., Regular graphs of odd degree are antimagic, J. Graph Theory, 80, 28-33 (2015) · Zbl 1321.05229
[6] Eccles, T., Graphs of large linear size are antimagic, J. Graph Theory, 81, 236-261 (2016) · Zbl 1333.05264
[7] Gallian, J. A., A dynamic survey of graph labeling, Electron. J. Combin., DS6 (2016)
[8] Hartsfield, N.; Ringel, G., Pearls in Graph Theory, 108-109 (1990), Academic Press: Academic Press Boston, (revised version, 1994) · Zbl 0703.05001
[9] Hefetz, D.; Mütze, T.; Schwartz, J., On antimagic directed graphs, J. Graph Theory, 64, 219-232 (2010) · Zbl 1209.05213
[10] Li, T.; Song, Z.-X.; Wang, G.; Yang, D.; Zhang, C.-Q., Antimagic orientations of even regular graphs, J. Graph Theory, 90, 46-53 (2019) · Zbl 1441.05200
[11] Shan, S.; Yu, X., Antimagic orientation of biregular bipartite graphs, Electron. J. Combin., 24 (2017), Paper 4.31 · Zbl 1373.05166
[12] Yang, D., A note on antimagic orientations of even regular graphs, Discrete Appl. Math., 267, 224-228 (2019) · Zbl 1419.05190
[13] Yilma, Z. B., Antimagic properties of graphs with large maximum degree, J. Graph Theory, 72, 367-373 (2013) · Zbl 1261.05092
[14] Yu, X.; Chang, Y.; Zhou, S., Antimagic orientation of Halin graphs, Discrete Math., 342, 3160-3165 (2019) · Zbl 1419.05191
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.