Back to Search
Start Over
Interval edge colorings of the generalized lexicographic product of some graphs
- Source :
- AIMS Mathematics, Vol 9, Iss 11, Pp 30597-30611 (2024)
- Publication Year :
- 2024
- Publisher :
- AIMS Press, 2024.
-
Abstract
- 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] $.
Details
- Language :
- English
- ISSN :
- 24736988
- Volume :
- 9
- Issue :
- 11
- Database :
- Directory of Open Access Journals
- Journal :
- AIMS Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- edsdoj.bdf1dfd4ac894136afb68ebd602c4c15
- Document Type :
- article
- Full Text :
- https://doi.org/10.3934/math.20241477?viewType=HTML