Research article

A new vertex distinguishing total coloring of trees

  • Received: 26 February 2021 Accepted: 16 June 2021 Published: 23 June 2021
  • MSC : 05C15

  • Let $ f $ be a proper total $ k $-coloring of a simple graph $ G $ from $ V(G)\cup E(G) $ to $ \{1, 2, \dots, k\} $, let $ C(u, f) $ be the set of the colors assigned to the edges incident with $ u $, and let $ n_d(G) $ and $ \Delta(G) $ denote the number of all vertices of degree $ d $ and the maximum degree in $ G $, respectively. We call $ f $ a (2)-vertex distinguishing total $ k $-coloring ($ k $-(2)-vdc for short) if $ C(u, f)\neq C(v, f) $ and $ C(u, f)\cup \{f(u)\}\neq C(v, f)\cup \{f(v)\} $ for distinct vertices $ u, v\in V(G) $. The minimum number $ k $ of colors required for which $ G $ admits a $ k $-(2)-vdc is denoted by $ \chi''_{2s}(G) $. In this paper, we show that a tree $ T $ with $ n_2(T)\leq n_1(T) $ has $ \chi''_{2s}(T) = n_1(T) $ if and only if $ T $ is not a tree with $ D(T) = 2, 3 $ or $ n_1(T) = \Delta(T) $, where $ D(T) $ is the diameter of tree $ T $.

    Citation: Chao Yang, Bing Yao, Zhi-xiang Yin. A new vertex distinguishing total coloring of trees[J]. AIMS Mathematics, 2021, 6(9): 9468-9475. doi: 10.3934/math.2021550

    Related Papers:

  • Let $ f $ be a proper total $ k $-coloring of a simple graph $ G $ from $ V(G)\cup E(G) $ to $ \{1, 2, \dots, k\} $, let $ C(u, f) $ be the set of the colors assigned to the edges incident with $ u $, and let $ n_d(G) $ and $ \Delta(G) $ denote the number of all vertices of degree $ d $ and the maximum degree in $ G $, respectively. We call $ f $ a (2)-vertex distinguishing total $ k $-coloring ($ k $-(2)-vdc for short) if $ C(u, f)\neq C(v, f) $ and $ C(u, f)\cup \{f(u)\}\neq C(v, f)\cup \{f(v)\} $ for distinct vertices $ u, v\in V(G) $. The minimum number $ k $ of colors required for which $ G $ admits a $ k $-(2)-vdc is denoted by $ \chi''_{2s}(G) $. In this paper, we show that a tree $ T $ with $ n_2(T)\leq n_1(T) $ has $ \chi''_{2s}(T) = n_1(T) $ if and only if $ T $ is not a tree with $ D(T) = 2, 3 $ or $ n_1(T) = \Delta(T) $, where $ D(T) $ is the diameter of tree $ T $.



    加载中


    [1] P. N. Balister, A. Kostochka, H. Li, R. H. Schelp, Balanced edge colorings, J. Comb. Theory B, 90 (2004), 3–20. doi: 10.1016/S0095-8956(03)00073-X
    [2] P. N. Balister, B. Bollob$\acute{a}$s, R. H. Schelp, Vertex distinguishing coloring of graphs with $\Delta(G)$ = 2, Discrete Math., 252 (2002), 17–29. doi: 10.1016/S0012-365X(01)00287-4
    [3] A. C. Burris, R. H. Schelp, Vertex-distingushing proper edge-colorings, J. Graph Theory, 26 (1997), 73–82. doi: 10.1002/(SICI)1097-0118(199710)26:2<73::AID-JGT2>3.0.CO;2-C
    [4] J. Černý, M. Horňák, R. Soták, Observability of a graph, Math. Slovaca, 46 (1996), 21–31.
    [5] B. Yao, Z. F. Zhang, J. F. Wang, Some results on spanning trees, Acta Math. Appl. Sin. Engl. Ser., 26 (2010), 607–616. doi: 10.1007/s10255-010-0011-4
  • Reader Comments
  • © 2021 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(1840) PDF downloads(49) Cited by(0)

Article outline

Figures and Tables

Figures(5)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog