Research article

Interval edge colorings of the generalized lexicographic product of some graphs

  • Received: 08 July 2024 Revised: 26 August 2024 Accepted: 16 October 2024 Published: 28 October 2024
  • MSC : 05C15

  • An edge-coloring of a graph $ G $ with colors $ 1, \ldots, t $ is an interval $ t $-coloring if all colors are used and the colors of edges incident to each vertex of $ G $ are distinct and form an interval of integers. A graph $ G $ is interval colorable if it has an interval $ t $-coloring for some positive integer $ t $. For an interval colorable graph $ G $, the least and the greatest values of $ t $ for which $ G $ has an interval $ t $-coloring are denoted by $ w(G) $ and $ W(G) $. Let $ G $ be a graph with vertex set $ V(G) = \{u_1, \ldots, u_{m}\} $, $ m\geq2 $, and let $ h_m = (H_i)_{i\in\{1, \ldots, m\}} $ be a sequence of vertex-disjoint with $ V(H_i) = \{x_1^{(i)}, \ldots, x_{n_i}^{(i)}\} $, $ n_i\geq 1 $. The generalized lexicographic products $ G[h_m] $ of $ G $ and $ h_m $ is a simple graph with vertex set $ \cup_{i = 1}^{m}V(H_i) $, in which $ x_p^{(i)} $ is adjacent to $ x_q^{(j)} $ if and only if either $ u_i = u_j $ and $ x_p^{(i)}x_q^{(i)}\in E(H_i) $ or $ u_iu_j\in E(G) $. In this paper, we obtain several sufficient conditions for the generalized lexicographic product $ G[h_m] $ to have interval colorings. We also present some sharp bounds on $ w(G[h_m]) $ and $ W(G[h_m]) $ of $ G[h_m] $.

    Citation: Meiqin Jin, Ping Chen, Shuangliang Tian. Interval edge colorings of the generalized lexicographic product of some graphs[J]. AIMS Mathematics, 2024, 9(11): 30597-30611. doi: 10.3934/math.20241477

    Related Papers:

  • An edge-coloring of a graph $ G $ with colors $ 1, \ldots, t $ is an interval $ t $-coloring if all colors are used and the colors of edges incident to each vertex of $ G $ are distinct and form an interval of integers. A graph $ G $ is interval colorable if it has an interval $ t $-coloring for some positive integer $ t $. For an interval colorable graph $ G $, the least and the greatest values of $ t $ for which $ G $ has an interval $ t $-coloring are denoted by $ w(G) $ and $ W(G) $. Let $ G $ be a graph with vertex set $ V(G) = \{u_1, \ldots, u_{m}\} $, $ m\geq2 $, and let $ h_m = (H_i)_{i\in\{1, \ldots, m\}} $ be a sequence of vertex-disjoint with $ V(H_i) = \{x_1^{(i)}, \ldots, x_{n_i}^{(i)}\} $, $ n_i\geq 1 $. The generalized lexicographic products $ G[h_m] $ of $ G $ and $ h_m $ is a simple graph with vertex set $ \cup_{i = 1}^{m}V(H_i) $, in which $ x_p^{(i)} $ is adjacent to $ x_q^{(j)} $ if and only if either $ u_i = u_j $ and $ x_p^{(i)}x_q^{(i)}\in E(H_i) $ or $ u_iu_j\in E(G) $. In this paper, we obtain several sufficient conditions for the generalized lexicographic product $ G[h_m] $ to have interval colorings. We also present some sharp bounds on $ w(G[h_m]) $ and $ W(G[h_m]) $ of $ G[h_m] $.



    加载中


    [1] A. S. Asratian, R. R. Kamalian, Interval colorings of edges of a multigraph, Appl. Math., 5 (1987), 25–34. https://doi.org/10.48550/arXiv.1401.8079 doi: 10.48550/arXiv.1401.8079
    [2] A. S. Asratian, C. J. Casselgren, On interval edge colorings of $(\alpha, \beta)$-biregular bipartite graphs, Discrete Math., 307 (2007), 1951–1956. https://doi.org/10.1016/j.disc.2006.11.001 doi: 10.1016/j.disc.2006.11.001
    [3] J. A. Bondy, U. S. R. Murty, Graph theory with applications, London: Macmillan, 1976.
    [4] K. Giaro, M. Kubale, M. Małafiejski, Consecutive colorings of the edges of general graphs, Discrete Math., 236 (2001), 131–143. https://doi.org/10.1016/S0012-365X(00)00437-4 doi: 10.1016/S0012-365X(00)00437-4
    [5] A. Grzesik, H. Khachatrian, Interval edge-colorings of $K_{1, m, n}$, Discrete Appl. Math., 174 (2014), 140–145. https://doi.org/10.1016/j.dam.2014.04.003 doi: 10.1016/j.dam.2014.04.003
    [6] H. M. Hansen, Scheduling with minimum waiting periods, Master's Thesis, Odense University, Denmark, 1992.
    [7] I. Holyer, The NP-completeness of edge-coloring, SIAM J. Comput., 10 (1981), 718–720. https://doi.org/10.1137/0210055 doi: 10.1137/0210055
    [8] P. Jing, Z. Miao, Z. X. Song, Some remarks on interval colorings of complete tripartite and biregular graphs, Discrete Appl. Math., 277 (2020), 193–197. https://doi.org/10.1016/j.dam.2019.08.024 doi: 10.1016/j.dam.2019.08.024
    [9] R. R. Kamalian, Interval colorings of complete bipartite graphs and trees, Preprint of the Computing Centre of the Academy of Sciences of Armenia, 1989. https://doi.org/10.48550/arXiv.1308.2541
    [10] R. R. Kamalian, Interval edge colorings of graphs, Doctoral Thesis, Novosibirsk, 1990.
    [11] R. R. Kamalian, P. A. Petrosyan, A note on upper bounds for the maximum span in interval edge-colorings of graphs, Discrete Math., 312 (2012), 1393–1399. https://doi.org/10.1016/j.disc.2012.01.005
    [12] P. A. Petrosyan, Interval edge-colorings of Möbius ladders, In: Proceedings of the CSIT Conference, 2005,146–149. https://doi.org/10.48550/arXiv.0801.0159
    [13] P. A. Petrosyan, Interval edge-colorings of complete graphs and $n$-dimensional cubes, Discrete Math., 310 (2010), 1580–1587. doi:10.1016/j.disc.2010.02.001
    [14] P. A. Petrosyan, Interval edge colorings of some products of graphs, Discuss. Math. Graph T., 31 (2011), 357–373.
    [15] P. A. Petrosyan, H. H. Khachatrian, L. E. Yepremyan, H. G. Tananyan, Interval edge-colorings of graph products, In: Proceedings of the CSIT Conference, 2011, 89–92. https://doi.org/10.48550/arXiv.1110.1165
    [16] S. V. Sevastjanov, Interval colorability of the edges of a bipartite graph, Metody Diskretnogo Analiza, 50 (1990), 61–72.
    [17] V. Samodivkin, Domination related parameters in the generalized lexicographic product of graphs, Discrete Appl. Math., 300 (2021), 77-84. https://doi.org/10.1016/j.dam.2021.03.015 doi: 10.1016/j.dam.2021.03.015
    [18] H. H. Tepanyan, P. A. Petrosyan, Interval edge-colorings of composition of graphs, Discrete Appl. Math., 217 (2017), 368–374. https://doi.org/10.1016/j.dam.2016.09.022 doi: 10.1016/j.dam.2016.09.022
    [19] V. G. Vizing, On an estimate of the chromatic class of a p-graph, Discret Analiz, 3 (1964), 25–30.
  • Reader Comments
  • © 2024 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(123) PDF downloads(34) Cited by(0)

Article outline

Figures and Tables

Figures(1)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog