Research article

Neighbor full sum distinguishing total coloring of Halin graphs

  • Received: 11 October 2021 Revised: 11 January 2022 Accepted: 21 January 2022 Published: 28 January 2022
  • MSC : 05C15

  • Let $ f: V(G)\cup E(G)\rightarrow \{1, 2, \dots, k\} $ be a total $ k $ -coloring of $ G $. Define a weight function on total coloring as

    $ \phi(x) = f(x)+\sum\limits_{e\ni x}f(e)+\sum\limits_{y\in N(x)}f(y), $

    where $ N(x) = \{y\in V(G)|xy\in E(G)\} $. If $ \phi(x)\neq \phi(y) $ for any edge $ xy\in E(G) $, then $ f $ is called a neighbor full sum distinguishing total $ k $ -coloring of $ G $. The smallest value $ k $ for which $ G $ has such a coloring is called the neighbor full sum distinguishing total chromatic number of $ G $ and denoted by fgndi $ _{\sum}(G) $. Suppose that $ H = T\cup C $ is a Halin graph, where $ T $ and $ C $ are called the characteristic tree and the adjoint cycle, respectively. Let $ V_0\subseteq V(H)\setminus V(C) $ and each vertex in $ V_0 $ is adjacent to some vertices on $ C $. In this paper, we prove that the neighbor full sum distinguishing total chromatic number of two types of Halin graphs are not more than three: (i) 3-regular Halin graphs and (ii) every vertex of $ V_0 $ of a Halin graph with degree at least 4. The above results support a conjecture that fgndi $ _{\sum}(G)\leq 3 $ for any connected graph $ G $ of order at least three (Chang et al., 2022).

    Citation: Yinwan Cheng, Chao Yang, Bing Yao, Yaqin Luo. Neighbor full sum distinguishing total coloring of Halin graphs[J]. AIMS Mathematics, 2022, 7(4): 6959-6970. doi: 10.3934/math.2022386

    Related Papers:

  • Let $ f: V(G)\cup E(G)\rightarrow \{1, 2, \dots, k\} $ be a total $ k $ -coloring of $ G $. Define a weight function on total coloring as

    $ \phi(x) = f(x)+\sum\limits_{e\ni x}f(e)+\sum\limits_{y\in N(x)}f(y), $

    where $ N(x) = \{y\in V(G)|xy\in E(G)\} $. If $ \phi(x)\neq \phi(y) $ for any edge $ xy\in E(G) $, then $ f $ is called a neighbor full sum distinguishing total $ k $ -coloring of $ G $. The smallest value $ k $ for which $ G $ has such a coloring is called the neighbor full sum distinguishing total chromatic number of $ G $ and denoted by fgndi $ _{\sum}(G) $. Suppose that $ H = T\cup C $ is a Halin graph, where $ T $ and $ C $ are called the characteristic tree and the adjoint cycle, respectively. Let $ V_0\subseteq V(H)\setminus V(C) $ and each vertex in $ V_0 $ is adjacent to some vertices on $ C $. In this paper, we prove that the neighbor full sum distinguishing total chromatic number of two types of Halin graphs are not more than three: (i) 3-regular Halin graphs and (ii) every vertex of $ V_0 $ of a Halin graph with degree at least 4. The above results support a conjecture that fgndi $ _{\sum}(G)\leq 3 $ for any connected graph $ G $ of order at least three (Chang et al., 2022).



    加载中


    [1] L. Addario-Berry, K. Dalal, C. McDiarmid, B. A. Reed, A. Thomason, Vertex-colouring edge-weightings, Combinatorica, 27 (2007), 1–12. https://doi.org/10.1007/s00493-007-0041-6 doi: 10.1007/s00493-007-0041-6
    [2] L. Addario-Berry, K. Dalal, B. A. Reed, Degree constrained subgraphs, Discrete Appl. Math., 156 (2008), 1168–1174. https://doi.org/10.1016/j.dam.2007.05.059 doi: 10.1016/j.dam.2007.05.059
    [3] J. A. Bondy, U. S. R. Murty, Graph theory, Springer, 2008.
    [4] G. J. Chang, C. H. Lu, J. J. Wu, Q. L. Yu, Vertex-coloring edge-weightings of graphs, Taiwan. J. Math., 15 (2011), 1807–1813. https://doi.org/10.11650/twjm/1500406380 doi: 10.11650/twjm/1500406380
    [5] J. Z. Chang, C. Yang, Z. X. Yin, B. Yao, An extension on neighbor sum distinguishing total coloring of graphs, arXiv Preprint, 2022. Available from: https://arXiv.org/abs/2201.02781.
    [6] E. Flandrin, H. Li, A. Marczyk, J. F. Saclé, M. Woźniak, A note on neighbor expanded sum distinguishing index, Discuss. Math. Graph T., 37 (2017), 29–37. https://doi.org/10.7151/dmgt.1909 doi: 10.7151/dmgt.1909
    [7] M. Kalkowski, A note on 1, 2-conjecture, Ph.D. Thesis, Poznan: Adam Mickiewicz University, 2009.
    [8] M. Kalkowski, M. Karoński, F. Pfender, Vertex-coloring edge weightings: Towards the 1-2-3-conjecture, J. Combin. Theory B, 100 (2010), 347–349. https://doi.org/10.1016/j.jctb.2009.06.002 doi: 10.1016/j.jctb.2009.06.002
    [9] M. Karoński, T. Łuczak, A. Thomason, Edge weights and vertex colours, J. Combin. Theory B, 91 (2004), 151–157. https://doi.org/10.1016/j.jctb.2003.12.001 doi: 10.1016/j.jctb.2003.12.001
    [10] K. W. Lih, D. D. F. Liu, On the strong chromatic index of cubic Halin graphs, Appl. Math. Lett., 25 (2012), 898–901. https://doi.org/10.1016/j.aml.2011.10.046 doi: 10.1016/j.aml.2011.10.046
    [11] J. Przybylo, M. Woźniak, On a 1, 2 conjecture, Discrete Math. Theor. Comput. Sci., 12 (2010), 101–108. https://doi.org/10.46298/dmtcs.491 doi: 10.46298/dmtcs.491
    [12] J. Przybylo, The 1-2-3 conjecture almost holds for regular graphs, J. Combin. Theory B, 147 (2021), 183–200. https://doi.org/10.1016/j.jctb.2020.03.005 doi: 10.1016/j.jctb.2020.03.005
    [13] W. C. Shiu, P. C. B. Lam, W. K. Tam, On strong chromatic index of Halin graph, J. Combin. Math. Combin. Comput., 57 (2006), 211–222.
    [14] J. Skowronek-Kaziów, 1, 2 conjecture-the multiplicative version, Inform. Process. Lett., 107 (2008), 93–95. https://doi.org/10.1016/j.ipl.2008.01.006 doi: 10.1016/j.ipl.2008.01.006
    [15] J. Skowronek-Kaziów, Multiplicative vertex-colouring weightings of graphs, Inform. Process. Lett., 112 (2012), 191–194. https://doi.org/10.1016/j.ipl.2011.11.009 doi: 10.1016/j.ipl.2011.11.009
    [16] T. Wang, Q. L. Yu, On vertex-coloring 13-edge-weighting, Front. Math. China, 3 (2008), 581–587. https://doi.org/10.1007/s11464-008-0041-x doi: 10.1007/s11464-008-0041-x
    [17] E. Q. Zhu, C. J. Liu, J. G. Yu, Neighbor product distinguishing total colorings of 2-degenerate graphs, J. Comb. Optim., 39 (2020), 72–76. https://doi.org/10.1007/s10878-019-00455-5 doi: 10.1007/s10878-019-00455-5
    [18] E. Q. Zhu, F. Jiang, C. J. Liu, J. Xu, Partition independent set and reduction-based approach for partition coloring problem, IEEE T. Cybernetics, 2020, 1–10. https://doi.org/10.1109/TCYB.2020.3025819 doi: 10.1109/TCYB.2020.3025819
  • Reader Comments
  • © 2022 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(1849) PDF downloads(160) Cited by(0)

Article outline

Figures and Tables

Figures(4)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog