On the Neighbor-Distinguishing Indices of Planar Graphs

被引:0
|
作者
Weifan Wang
Wenjing Xia
Jingjing Huo
Yiqiao Wang
机构
[1] Zhejiang Normal University,Department of Mathematics
[2] Hebei University of Engineering,Department of Mathematics
[3] Beijing University of Chinese Medicine,School of Management
来源
Bulletin of the Malaysian Mathematical Sciences Society | 2022年 / 45卷
关键词
Neighbor-distinguishing edge coloring; Planar graph; Maximum degree; Discharging method; 05C15;
D O I
暂无
中图分类号
学科分类号
摘要
Let G\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textit{G}$$\end{document} be a simple graph with no isolated edges. The neighbor-distinguishing edge coloring of G\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textit{G}$$\end{document} is a proper edge coloring of G\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textit{G}$$\end{document} such that any pair of adjacent vertices have different sets consisting of colors assigned on their incident edges. The neighbor-distinguishing index of G\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textit{G}$$\end{document}, denoted by χa′(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\chi '_{a}(G)$$\end{document}, is the minimum number of colors in such an edge coloring of G\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textit{G}$$\end{document}. In this paper, we show that if G\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textit{G}$$\end{document} is a connected planar graph with maximum degree Δ≥14\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Delta \ge 14$$\end{document}, then Δ≤χa′(G)≤Δ+1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Delta \le \chi '_a(G)\le \Delta +1$$\end{document}, and χa′(G)=Δ+1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\chi '_a(G)=\Delta +1$$\end{document} if and only if G\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textit{G}$$\end{document} contains a pair of adjacent vertices of maximum degree. This improves a result in [W. Wang, D. Huang, A characterization on the adjacent vertex distinguishing index of planar graphs with large maximum degree, SIAM J. Discrete Math. 29(2015), 2412–2431], which says that every connected planar graph G\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textit{G}$$\end{document} with Δ≥16\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Delta \ge 16$$\end{document} has Δ≤χa′(G)≤Δ+1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Delta \le \chi '_a(G)\le \Delta +1$$\end{document}, and χa′(G)=Δ+1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\chi '_a(G)=\Delta +1$$\end{document} if and only if G\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textit{G}$$\end{document} contains a pair of adjacent vertices of maximum degree.
引用
收藏
页码:677 / 696
页数:19
相关论文
共 50 条
  • [41] Neighbor sum distinguishing total choosability of planar graphs without adjacent special 5-cycles
    Sun, Lin
    DISCRETE APPLIED MATHEMATICS, 2020, 279 : 146 - 153
  • [42] Neighbor sum distinguishing total coloring of planar graphs without 4-cycles
    Hongjie Song
    Changqing Xu
    Journal of Combinatorial Optimization, 2017, 34 : 1147 - 1158
  • [43] Neighbor sum distinguishing total coloring of planar graphs without 5-cycles
    Ge, Shan
    Li, Jianguo
    Xu, Changqing
    THEORETICAL COMPUTER SCIENCE, 2017, 689 : 169 - 175
  • [44] Neighbor sum distinguishing total coloring of planar graphs without 4-cycles
    Song, Hongjie
    Xu, Changqing
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2017, 34 (04) : 1147 - 1158
  • [45] Neighbor Sum Distinguishing Total Choosability of Planar Graphs with Maximum Degree at Least 10
    Dong-han Zhang
    You Lu
    Sheng-gui Zhang
    Li Zhang
    Acta Mathematicae Applicatae Sinica, English Series, 2024, 40 : 211 - 224
  • [46] NEIGHBOR PRODUCT DISTINGUISHING TOTAL COLORINGS OF PLANAR GRAPHS WITH MAXIMUM DEGREE AT LEAST TEN
    Dong, Aijun
    Li, Tong
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2021, 41 (04) : 981 - 999
  • [47] Neighbor sum distinguishing total chromatic number of planar graphs with maximum degree 10
    Yang, Donglei
    Sun, Lin
    Yu, Xiaowei
    Wu, Jianliang
    Zhou, Shan
    APPLIED MATHEMATICS AND COMPUTATION, 2017, 314 : 456 - 468
  • [48] Neighbor Sum Distinguishing Total Choosability of Planar Graphs with Maximum Degree at Least 10
    Zhang, Dong-han
    Lu, You
    Zhang, Sheng-gui
    Zhang, Li
    ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES, 2024, 40 (01): : 211 - 224
  • [49] Neighbor Sum Distinguishing Total Coloring of Triangle Free IC-planar Graphs
    Song, Wen Yao
    Duan, Yuan Yuan
    Miao, Lian Ying
    ACTA MATHEMATICA SINICA-ENGLISH SERIES, 2020, 36 (03) : 292 - 304
  • [50] Neighbor Sum Distinguishing Total Coloring of Triangle Free IC-planar Graphs
    Wen Yao SONG
    Yuan Yuan DUAN
    Lian Ying MIAO
    Acta Mathematica Sinica,English Series, 2020, 36 (03) : 292 - 304