Colour Class Domination equivalence partition and Colourful resolving sets in graphs

Abstract

Let H = (V, E) be a simple graph. A subset S of V (H) is an equivalence set if the subgraph induced by S is component-wise complete. Let P = {V1, V2, · · · , Vk} be a partition of V (H) where each Vi , 1 ≤ i ≤ k is an equivalence set of H. The partition P is called a colourful domination equivalence partition if the set D = {u1, u2, · · · , uk} where ui , 1 ≤ i ≤ k are suitably chosen vertices one each from Vi , 1 ≤ i ≤ k is a dominating set. The trivial partition where every partite set is a singleton is an example of a colourful domination equivalence partition. The minimum cardinality of such a partition is called colourful domination equivalence partition number of G and is denoted by χγeq (H). A subset S = {u1, u2, · · · , ur} of V (H) is called a resolving set of H if for any v in V (H), the code of v with respect to S namely (d(v, u1), · · · , d(v, ur)) (denoted by cS(v)) is distinct for distinct v where d(v, ui) denotes the distance between v and ui. Since u1, · · · , ur are evidently resolved by S, it is enough if vertices in V − S are resolved by S. Given a proper colour partition P = {V1, V2, · · · , Vk}, a resolving set S = {u1, u2, · · · , uk} is said to be colourful with respect to P if ui ∈ Vi for every i, 1 ≤ i ≤ k. A proper colour partition P is said to be a colour resolving colour partition if some set of vertices, one each from each colour class is a revolving set. The minimum cardinality of a resolving set of H is called the metric dimension of G [8] and is denoted by Dim(H). The trivial partition consisting of n singletons where n is the order of H is a colourful resolving colour partition of H. The minimum cardinality of a colourful resolving colour partition of H is denoted by χre(H). A study of these two new parameters is initiated in this paper.