Research article

Injective edge coloring of generalized Petersen graphs

  • Received: 07 January 2021 Accepted: 11 May 2021 Published: 19 May 2021
  • MSC : 05C15

  • Three edges $ e_1 $, $ e_2 $ and $ e_3 $ in a graph $ G $ are $ consecutive $ if they form a cycle of length $ 3 $ or a path in this order. A $ k $-$ injective\; edge\; coloring $ of a graph $ G $ is an edge coloring of $ G $, (not necessarily proper), such that if edges $ e_1 $, $ e_2 $, $ e_3 $ are consecutive, then $ e_1 $ and $ e_3 $ receive distinct colors. The minimum $ k $ for which $ G $ has a $ k $-injective edge coloring is called the $ injective\; edge\; coloring\; number $, denoted by $ \chi_i^{\prime}(G) $. In this paper, we consider the injective edge coloring numbers of generalized Petersen graphs $ P(n, 1) $ and $ P(n, 2) $. We determine the exact values of injective edge coloring numbers for $ P(n, 1) $ with $ n\geq 3 $, and for $ P(n, 2) $ with $ 4\leq n\leq 7 $. For $ n\geq 8 $, we show that $ 4\leq \chi_{i}^{'}(P(n, 2))\leq 5. $

    Citation: Yanyi Li, Lily Chen. Injective edge coloring of generalized Petersen graphs[J]. AIMS Mathematics, 2021, 6(8): 7929-7943. doi: 10.3934/math.2021460

    Related Papers:

  • Three edges $ e_1 $, $ e_2 $ and $ e_3 $ in a graph $ G $ are $ consecutive $ if they form a cycle of length $ 3 $ or a path in this order. A $ k $-$ injective\; edge\; coloring $ of a graph $ G $ is an edge coloring of $ G $, (not necessarily proper), such that if edges $ e_1 $, $ e_2 $, $ e_3 $ are consecutive, then $ e_1 $ and $ e_3 $ receive distinct colors. The minimum $ k $ for which $ G $ has a $ k $-injective edge coloring is called the $ injective\; edge\; coloring\; number $, denoted by $ \chi_i^{\prime}(G) $. In this paper, we consider the injective edge coloring numbers of generalized Petersen graphs $ P(n, 1) $ and $ P(n, 2) $. We determine the exact values of injective edge coloring numbers for $ P(n, 1) $ with $ n\geq 3 $, and for $ P(n, 2) $ with $ 4\leq n\leq 7 $. For $ n\geq 8 $, we show that $ 4\leq \chi_{i}^{'}(P(n, 2))\leq 5. $



    加载中


    [1] M. Alaeiyan, H. Karami, Perfect 2-colorings of the generalized Petersen graph, Proc. Indian Acad. Sci. Math. Sci., 126 (2016), 289–294. doi: 10.1007/s12044-016-0285-4
    [2] A. A. Bertossi, M. A. Bonuccelli, Code assignment for hidden terminal interference avoidance in multihop packet radio networks, IEEE/ACM Trans. Networking, 3 (1995), 441–449. doi: 10.1109/90.413218
    [3] Y. Bu, W. Chen, Injective-edge coloring of planar graphs with girth at least 6, Journal of Zhejiang Normal University, 43 (2020), 19–25 (In Chinese).
    [4] Y. Bu, C. Qi, J. Zhu, Injective edge coloring of planar graphs, Adv. Math., 6 (2020), 675–684(In Chinese).
    [5] Y. Bu, C. Qi, Injective edge coloring of sparse graphs, Discrete Mathematics, Algorithms and Applications, 10 (2018), 1850022. doi: 10.1142/S1793830918500222
    [6] D. M. Cardoso, J. O. Cerdeira, J. P. Cruz, C. Dominic, Injective edge coloring of graphs, Filomat, 33 (2019), 6411–6423. doi: 10.2298/FIL1919411C
    [7] B. Ferdjallah, S. Kerdjoudj, A. Raspaud, Injective edge-coloring of sparse graphs, arXiv: 1907.0983v2 [math.CO], 2019.
    [8] G. Hahn, J. Kratochv$\acute{i}$l, J. Sir$\acute{a}$, D. Sotteau, On the injective chromatic number of graphs, Discrete Math., 256 (2002), 179–192. doi: 10.1016/S0012-365X(01)00466-6
    [9] A. Kostochka, A. Raspaud, J. Xu, Injective edge-coloring of graphs with given maximum degree, Eur. J. Combin., 96 (2021), 103355. doi: 10.1016/j.ejc.2021.103355
    [10] Z. Yang, B. Wu, Strong edge chromatic index of the generalized Petersen graphs, Appl. Math. Comput., 321 (2018), 431–441.
    [11] J. Yue, S. Zhang, X. Zhang, Note on the perfect EIC-graphs, Appl. Math. Comput., 289 (2016), 481–485.
    [12] E. Zhu, Z. Li, Z. Shao, J. Xu, C. Liu, Acyclic 3-coloring of generalized Petersen graphs, J. Comb. Optim., 31 (2016), 902–911. doi: 10.1007/s10878-014-9799-9
  • 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(2854) PDF downloads(225) Cited by(4)

Article outline

Figures and Tables

Figures(20)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog