×

Local antimagic orientations of \(d\)-degenerate graphs. (English) Zbl 1406.05088

Summary: A \(k\)-antimagic labeling of a digraph \(D\) with \(n\) vertices and \(m\) arcs is an injection from the set of arcs of \(D\) to the integers \(\{1, \ldots, m + k \}\) such that all \(n\) vertex-sums are pairwise distinct, where the vertex-sum of a vertex \(v\) is the sum of labels of all arcs entering \(v\) minus the sum of labels of all arcs leaving \(v\). An orientation \(D\) of a graph \(G\) is called \(k\)-antimagic if \(D\) has a \(k\)-antimagic labeling. D. Hefetz et al. [J. Graph Theory 64, No. 3, 219–232 (2010; Zbl 1209.05213)] conjectured that every connected graph admits an antimagic orientation, where “antimagic” is short for “0-antimagic”. In this paper, we consider local \(k\)-antimagic orientations of graphs. An orientation \(D\) of a graph \(G\) is called local \(k\)-antimagic if there is an injective edge labeling from \(E(G)\) to \(\{1, \ldots, | E(G) | + k \}\) such that any two adjacent vertices of \(D\) have different vertex-sums. We prove that every \(d\)-degenerate graph admits a local \((d + 2)\)-antimagic orientation.

MSC:

05C78 Graph labelling (graceful graphs, bandwidth, etc.)
05C20 Directed graphs (digraphs), tournaments

Citations:

Zbl 1209.05213
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alon, N., Combinatorial nullstellensatz, Combin. Probab. Comput., 8, 1-2, 7-29 (1999) · Zbl 0920.05026
[2] Alon, N.; Kaplan, G.; Lev, A.; Roditty, Y.; Yuster, R., Dense graphs are antimagic, J. Graph Theory, 47, 297-309 (2004) · Zbl 1055.05132
[3] Bartnicki, T.; Grytczuk, J.; Niwczyk, S., Weight choosability of graphs, J. Graph Theory, 60, 3, 242-256 (2009) · Zbl 1210.05138
[4] Bensmail, J.; Senhaji, M.; Lyngsie, K. S., On a combination of the 1-2-3 conjecture and the antimagic labelling conjecture, Discrete Math. Theor. Comput. Sci., 19 (2017) · Zbl 1400.05102
[5] Z. Berikkyzy, A. Brandt, S. Jahanbekam, V. Larsen, D. Rorabaugh, Antimagic labelings of weighted and oriented graphs, arXiv:1510.05070v1; Z. Berikkyzy, A. Brandt, S. Jahanbekam, V. Larsen, D. Rorabaugh, Antimagic labelings of weighted and oriented graphs, arXiv:1510.05070v1
[6] Borowiecki, M.; Grytczuk, J.; Pilśniak, M., Coloring chip configurations on graphs and digraphs, Inform. Process. Lett., 112, 1-4 (2012) · Zbl 1232.05074
[7] Y. Chang, F. Jing, G. Wang, Local antimagic orientation of graphs, private communication.; Y. Chang, F. Jing, G. Wang, Local antimagic orientation of graphs, private communication.
[8] Eccles, T., Graphs of large linear size are antimagic, J. Graph Theory, 81, 3, 236-261 (2016) · Zbl 1333.05264
[9] Gallian, J. A., A dynamic survey of graph labeling, Electron. J. Combin. (1997)
[10] Hartsfield, N.; Ringel, G., Pearls in Graph Theory, 108-109 (1990), Academic Press: Academic Press INC, Boston, Revised version 1994
[11] Haslegrave, J., Proof of a local antimagic conjecture, Discrete Math. Theor. Comput. Sci., 20 (2018) · Zbl 1401.05260
[12] Hefetz, D.; Mütze, T.; Schwartz, J., On antimagic directed graphs, J. Graph Theory, 64, 3, 219-232 (2010) · Zbl 1209.05213
[13] Kalkowski, M.; Karoński, M.; Pfender, F., Vertex-coloring edge-weightings: Towards the 1-2-3 conjecture, J. Combin. Theory Ser. B, 100, 347-349 (2010) · Zbl 1209.05087
[14] Karoński, M.; Łuczak, T.; Thomason, A., Edge weights and vertex colours, J. Combin. Theory Ser. B, 91, 151-157 (2004) · Zbl 1042.05045
[15] Khatirinejad, M.; Naserasr, R.; Newman, M.; Seamone, B.; Stevens, B., Digraphs are 2-weight choosable, Electron. J. Combin., 18, 1 (2001) · Zbl 1205.05101
[16] Li, T.; Song, Z.-X.; Wang, G.; Yang, D.; Zhang, C.-Q., Antimagic orientation of even regular graphs, J. Graph Theory (2018)
[17] Liang, Y.-C.; Wong, T.-L.; Zhu, X., Anti-magic labeling of trees, Discrete Math., 331, 9-14 (2014) · Zbl 1297.05205
[18] Przybyło, J.; Wong, T.-L., Neighbor distinguishing edge colorings via the combinatorial nullstellensatz revisited, J. Graph Theory, 80, 4, 299-312 (2015) · Zbl 1330.05075
[19] Scheim, E., The number of edge 3-colorings of a planar cubic graph as a permanent, Discrete Math., 8, 377-382 (1974) · Zbl 0281.05103
[20] Shan, S.; Yu, X., Antimagic orientation of biregular bipartite graphs, Electron. J. Combin., 24, 4, #P4.31 (2017) · Zbl 1373.05166
[21] Yilma, Z. B., Antimagic properties of graphs with large maximum degree, J. Graph Theory, 72, 4, 367-373 (2013) · Zbl 1261.05092
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.