Neighbor-sum-distinguishing edge choosability of subcubic graphs

被引:0
作者
Jingjing Huo
Yiqiao Wang
Weifan Wang
机构
[1] Soochow University,Department of Mathematics
[2] Hebei University of Engineering,Department of Mathematics
[3] Beijing University of Chinese Medicine,School of Management
[4] Zhejiang Normal University,Department of Mathematics
来源
Journal of Combinatorial Optimization | 2017年 / 34卷
关键词
Subcubic graph; List neighbor-sum-distinguishing edge coloring; Maximum average degree; Combinatorial Nullstellensatz; 05C15;
D O I
暂无
中图分类号
学科分类号
摘要
A graph G is said to be neighbor-sum-distinguishing edge k-choose if, for every list L of colors such that L(e) is a set of k positive real numbers for every edge e, there exists a proper edge coloring which assigns to each edge a color from its list so that for each pair of adjacent vertices u and v the sum of colors taken on the edges incident to u is different from the sum of colors taken on the edges incident to v. Let ch∑p′(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm{ch}^{\prime }_{\sum ^p}(G)$$\end{document} denote the smallest integer k such that G is neighbor-sum-distinguishing edge k-choose. In this paper, we prove that if G is a subcubic graph with the maximum average degree mad(G), then (1) ch∑p′(G)≤7\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm{ch}^{\prime }_{\sum ^p}(G)\le 7$$\end{document}; (2) ch∑p′(G)≤6\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm{ch}^{\prime }_{\sum ^p}(G)\le 6$$\end{document} if mad(G)<3613\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\hbox {mad}(G)<\frac{36}{13}$$\end{document}; (3) ch∑p′(G)≤5\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm{ch}^{\prime }_{\sum ^p}(G)\le 5$$\end{document} if mad(G)<52\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\hbox {mad}(G)<\frac{5}{2}$$\end{document}.
引用
收藏
页码:742 / 759
页数:17
相关论文
共 17 条
[1]  
Alon N(1999)Combinatorial nullstellensatz Comb Probab Comput 8 7-29
[2]  
Flandrin E(2013)Neighbor sum distinguishing index Graphs Comb. 29 1329-1336
[3]  
Marczyk A(2015)Asymptotically optimal neighbour sum distinguishing colourings of graphs Random Struct Algorithms 47 776-791
[4]  
Przybyło J(2013)Neighbor distinguishing edge colorings via the Combinatorial Nullstellensatz SIAM J Discrete Math 27 1313-1322
[5]  
Saclé JF(2015)Neighbor distinguishing edge colorings via the Combinatorial Nullstellensatz revisited J Graph Theory 80 299-312
[6]  
Wońzniak M(2014)Neighbor sum distinguishing index of planar graphs Discrete Math 334 70-73
[7]  
Przybyło J(2010)Adjacent vertex distinguishing edge-colorings of graphs with smaller maximum average degree J Comb Optim 19 471-485
[8]  
Przybyło J(2014)An improved upper bound for the neighbor sum distinguishing index of graphs Discrete Appl Math 175 126-128
[9]  
Przybyło J(undefined)undefined undefined undefined undefined-undefined
[10]  
Wong T(undefined)undefined undefined undefined undefined-undefined