Local antimagic orientation of graphs

被引:0
作者
Yulin Chang
Fei Jing
Guanghui Wang
机构
[1] Shandong University,School of Mathematics
来源
Journal of Combinatorial Optimization | 2020年 / 39卷
关键词
Antimagic orientation; Local antimagic orientation; Combinatorial Nullstellensatz;
D O I
暂无
中图分类号
学科分类号
摘要
An antimagic labelling of a digraph D with m arcs is a bijection from the set of arcs of D to {1,…,m}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\{1,\ldots ,m\}$$\end{document} such that any two vertices have distinct vertex-sums, where the vertex-sum of a vertex v∈V(D)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$v\in V(D)$$\end{document} 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 antimagic if D has an antimagic labelling. In 2010, Hefetz, Mu¨\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ddot{\text {u}}$$\end{document}tze and Schwartz conjectured that every connected graph admits an antimagic orientation. The conjecture is still open, even for trees. Motivated by directed version of the well-known 1-2-3 Conjecture, we deal with vertex-sums such that only adjacent vertices must be distinguished. An orientation D of a graph G is local antimagic if there is a bijection from E(G) to {1,…,|E(G)|}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\{1,\ldots ,|E(G)|\}$$\end{document} such that any two adjacent vertices have distinct vertex-sums. We prove that every graph with maximum degree at most 4 admits a local antimagic orientation by Alon’s Combinatorial Nullstellensatz.
引用
收藏
页码:1129 / 1152
页数:23
相关论文
共 46 条
[1]  
Alon N(1999)Combinatorial Nullstellensatz Comb Probab Comput 8 7-29
[2]  
Alon N(2004)Dense graphs are antimagic J Graph Theory 47 297-309
[3]  
Kaplan G(2017)Local antimagic vertex coloring of a graph Graphs Comb 33 275-285
[4]  
Lev A(2017)On a combination of the 1-2-3 conjecture and the antimagic labelling conjecture Discrete Math Theor Comput Sci 19 21-4
[5]  
Roditty Y(2012)Coloring chip configurations on graphs and digraphs Inf Process Lett 112 1-349
[6]  
Yuster R(2016)Antimagic labelling of regular graphs J Graph Theory 82 339-182
[7]  
Arumugam S(2009)Regular bipartite graphs are antimagic J Graph Theory 60 173-33
[8]  
Premalatha K(2015)Regular graphs of odd degree are antimagic J Graph Theory 80 28-272
[9]  
Bača M(2018)Proof of a local antimagic conjecture Discrete Math Theor Comput Sci 20 18-82
[10]  
Semaničová-Feňovčíková A(2005)Anti-magic graphs via the combinatorial nullstellensatz J Graph Theory 50 263-232