Publications
Sort:
Open Access Research Article Issue
Interval edge colorings of the generalized lexicographic product of some graphs
AIMS Mathematics 2024, 9(11): 30597-30611
Published: 28 October 2024
Abstract PDF (283.7 KB) Collect
Downloads:40

An edge-coloring of a graph G with colors 1,…,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)={u1,…,um}, m≥2, and let hm=(Hi)i∈{1,…,m} be a sequence of vertex-disjoint with V(Hi)={x1(i),…,xni(i)}, ni≥1. The generalized lexicographic products G[hm] of G and hm is a simple graph with vertex set ∪i=1mV(Hi), in which xp(i) is adjacent to xq(j) if and only if either ui=uj and xp(i)xq(i)∈E(Hi) or uiuj∈E(G). In this paper, we obtain several sufficient conditions for the generalized lexicographic product G[hm] to have interval colorings. We also present some sharp bounds on w(G[hm]) and W(G[hm]) of G[hm].

Total 1