Publications
Sort:
Open Access Research Article Issue
Edge-coloring of generalized lexicographic product of graphs
AIMS Mathematics 2024, 9(6): 15988-15995
Published: 07 May 2024
Abstract PDF (335.9 KB) Collect
Downloads:19

An edge-coloring of a graph G is an assignment of colors to its edges so that no two edges incident to the same vertex receive the same color. The chromatic index of G, denoted by χ ′ ( G ), is the least k for which G has a k edge-coloring. Graphs with χ ′ ( G ) = Δ ( G ) are said to be Class 1, and graphs with χ ′ ( G ) = Δ ( G ) + 1 are said to be Class 2. Let G be a graph with V ( G ) = { t 1 , t 2 , … , t n }, n ≥ 2, and h n = ( H i ) i ∈ { 1 , 2 , … , n } be a sequence of vertex-disjoint graphs with V ( H i ) = { ( t i , y 1 ) , ( t i , y 2 ) , … , ( t i , y m i ) }, m i ≥ 1. The generalized lexicographic product G [ h n ] of G and h n = ( H i ) i ∈ { 1 , 2 , … , n } is a simple graph with vertex set ⋃ i = 1 n V ( H i ), in which ( t i , y p ) is adjacent to ( t j , y q ) if and only if either t i = t j and ( t i , y p ) ( t i , y q ) ∈ E ( H i ) or t i t j ∈ E ( G ). If G is a complete graph with order 2, then G [ h 2 ] denotes a join H 1 + H 2 of vertex-disjoint graphs H 1 and H 2 . If H i ≅ H for i = 1 , 2 , … , n, then G [ h n ] = G [ H ], where G [ H ] denotes the lexicographic product of two graphs G and H. In this paper, we provide sufficient conditions for the generalized lexicographic product G [ h n ] of G and h n = ( H i ) i ∈ { 1 , 2 , … , n } to be Class 1, where all graphs in h n have the same number of vertices.

Total 1