A Comparison on the Bounds of Chromatic Preserving Number and Dom-Chromatic Number of Cartesian Product and Kronecker Product of Paths

Abstract

Let G be a simple graph with vertex set V and edge set E. A Set S Í V is said to be a chromatic preserving set or a cp-set if χ(<S>) = χ(G) and the minimum cardinality of a cp-set in G is called the chromatic preserving number or cp-number of G and is denoted by cpn(G). A cp-set of cardinality cpn(G) is called a cpn-set. A subset S of V is said to be a dom- chromatic set (or a dc-set) if S is a dominating set and χ(<S>) = χ(G). The minimum cardinality of a dom-chromatic set in a graph G is called the dom-chromatic number (or dc- number) of G and is denoted by γ_ch(G). The Kronecker product G₁ Ù G₂ of two graphs G₁ = (V₁, E₁) and G₂ = (V₂, E₂) is the graph G with vertex set V₁ x V₂ and any two distinct vertices (u₁, v₁) and (u₂, v₂) of G are adjacent if u₁u₂ Î E₁ and v₁v₂ Î E₂. The Cartesian product G₁ x G₂ is the graph with vertex set V₁ x V₂ where any two distinct vertices (u₁, v₁) and (u₂, v₂) are adjacent whenever (i) u₁ = u₂ and v₁v₂ Î E₂ or (ii) u₁u₂ Î E₁ and v₁ = v₂. These two products have no common edges. They are almost like complements but not exactly. In this paper, we discuss the behavior of the cp-number and dc-number and their bounds for product of paths in the two cases. A detailed comparative study is also done.