Antimagic orientations of graphs with large maximum degree

DOI10.1016/J.DISC.2020.112123zbMATH Open1448.05178arXiv1908.06072OpenAlexW3082929499MaRDI QIDQ2005714FDOQ2005714

Z. X. Song, Xiaohong Zhang, K. E. Perry, Andrew Owens, Donglei Yang, Joshua Carlson, Fangfang Zhang, Inne Singgih

Publication date: 8 October 2020

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: Given a digraph $D$ with $m$ arcs, a bijection $au:A(D)ightarrow1,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 $au$ is the sum of labels of all arcs entering $u$ minus the sum of labels of all arcs leaving $u$. We say $(D,au)$ is an antimagic orientation of a graph $G$ if $D$ is an orientation of $G$ and $au$ is an antimagic labeling of $D$. Motivated by the conjecture of Hartsfield and Ringel from 1990 on antimagic labelings of graphs, Hefetz, M"{u}tze, and Schwartz in 2010 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 $nge9$ vertices with maximum degree at least $n-5$ admits an antimagic orientation.

Full work available at URL: https://arxiv.org/abs/1908.06072

zbMATH Keywords

antimagic labelingEuler tourantimagic orientation

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Dense graphs are antimagic
• Regular bipartite graphs are antimagic
• Antimagic Properties of Graphs with Large Maximum Degree
• On antimagic directed graphs
• Antimagic Labeling of Regular Graphs
• Regular graphs are antimagic
• Antimagic orientation of biregular bipartite graphs
• A note on antimagic orientations of even regular graphs
• Antimagic orientation of Halin graphs
• Graphs of large linear size are antimagic
• Antimagic orientations of even regular graphs
• Regular Graphs of Odd Degree Are Antimagic

Cited In (7)

• Antimagic orientation of subdivided caterpillars
• Antimagic orientation of graphs with minimum degree at least 33
• Antimagic labeling of biregular bipartite graphs
• Antimagic orientations of graphs with given independence number
• Antimagic orientation of forests
• Graph antimagic labeling: a survey
• Antimagic orientations of even regular graphs

This page was built for publication: Antimagic orientations of graphs with large maximum degree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2005714)