New concepts of domination in cubic graphs with application

1 Introduction

The research that Zadeh [71] conducted which focused on advancing the uncertainty theory led to the introduction of a new concept called fuzzy sets, which led to the many problems solution in areas such as topology, abstract algebra, geometry, graph theory, and analysis. This development is still ongoing in various branches. He later introduced a branch of fuzzy sets that showed the degree of membership, instead of assigning a number between 0 and 1 to each member of the set with an interval of numbers between 0 and 1. Zadeh’s ideas established many applications in various sciences such as decision analysis, information sciences, system sciences, control engineering, expert systems, pattern recognition, management sciences, etc. Kauffmann’s [23] ideas directed Rosenfeld [57] to introduce the concept of the fuzzy graph (FG). In FGs, fuzzy relations are introduced on fuzzy sets, which means that in addition to vertices, the edges are also in varying degrees between 0 and 1. Bhattacharya [6] presented some remarks on FGs and some operations on FGs were introduced by Mordeson and Peng [33]. Akram and Dudek [2] gave the idea of an interval-valued fuzzy graph (IVFG) in 2011. Atanassov [5] adopted the notion of membership and non-membership of an element in a set and proposed the idea of intuitionistic fuzzy sets (IFS). Talebi et al. [64–68] analyzed several concepts on FG and interval-valued intuitionistic fuzzy graph (IVIFG). Rashmanlou et al. [50–55] investigated novel concepts in fuzzy graphs. Other researchers have studied topics related to fuzzy graphs [4, 58].

Jun et al. [17] introduced the idea of the cubic set (CS) and it was characterized by interval-valued fuzzy set and fuzzy set, which is a more general tool to capture uncertainty and vagueness. Through applying this concept, we can solve various problems instigated by uncertainties and have the best choice by using CSs in decision-making. Jun et al. [20] combined neutrosophic set with CSs and proposed the Neutrosophic-CS idea, and defined different operations. He being aided by his colleagues also applied this concept to algebraic disciplines [15, 60]. Kang and Kim [22] investigated CSs mappings. Muhiuddin et al. [32] presented the stable-CSs idea. Rashid et al. [38] introduced the notion of a cubic graph (CG) where they introduced many new types of graphs and provided their application. Muhiuddin et al. [31] provided a modified definition of a CG. Kishore Kumar et al. [26] examined the regularity concept in CG. Other studies have been performed by some researchers in this regard [1, 70].

The concept of dominating set (DS) in graphs was inspired by the chess moves introduced by O.Ore [43]. The initial foundation of domination in graphs was laid by T.W. Haynes et al. [12]. The domination in FG was introduced by Somasundaram and Somasundaram [61, 62]. Gani et al. [35–42] conducted many studies on this concept. Gani and Chandrasekaran [35] introduced domination in FGs using strong edges. This concept was also studied by Mohideen and Ismayil [30]. Different definitions of domination in FGs were proposed and its different types were studied in FGs by researchers. Borzooei et al. [7, 69] described several concepts on vague graphs. Parvathi et al. [44] introduced the domination in an intuitionistic fuzzy graph (IFG).

In this paper, we introduce the domination and some of its properties in a CG by strong edges. Next, we introduce an independent cubic set (ICS) and examined its relationship with the DS. We also studied the domination of some of the most important CG operations. Finally, we present an application of domination in the emergency stairs of buildings.

2 Preliminaries

In this section, some basic concepts are reviewed to enter the main discussion.

A fuzzy set (FS) is a pair (V, σ) where V is a non-empty set and σ : V → [0, 1] is a membership function. For two FS σ₁ and σ₂, we define ( σ 1 ∧ σ 2 ) ( x ) = min { σ 1 ( x ) , σ 2 ( x ) } ( σ 1 ∨ σ 2 ) ( x ) = max { σ 1 ( x ) , σ 2 ( x ) } σ 1 ⊆ σ 2 ⇔ σ 1 ( x ) ≤ σ 2 ( x ) , ∀ x ∈ V . The complement of σ denoted by σ ¯ , is defined by σ ¯ ( x ) = 1 - σ ( x ) , ∀ x ∈ V . By an interval number we mean a closed subinterval [a, b] of [0, 1], where 0 ≤ a ≤ b ≤ 1. The interval number [a, a] is denoted by a. The set of interval numbers is denoted by D [0, 1]. For two interval number c₁ = [a₁, b₁] and c₂ = [a₂, b₂], we define r min { c 1 , c 2 } = [ min { a 1 , a 2 } , min { b 1 , b 2 } ] c 1 ≥ c 2 ⇔ a 1 ≥ a 2 and b 1 ≥ b 2 . The complement of c ∈ D [0, 1], denoted by c ¯ , is defined by c ¯ = [ 1 - b , 1 - a ] .

A function μ : V → D [0, 1] is called an interval-valued fuzzy set (IVFS) in V. For x ∈ V, μ (x) = [μ ^L  (x) , μ ^U  (x)] is called the membership degree of element x, where μ ^L , μ ^U  : V → [0, 1]. For every μ, ν ∈ D [0, 1], we define μ ⊆ ν ⇔ μ ( x ) ≤ ν ( x ) , ∀ x ∈ V . The complement of μ ¯ of μ ∈ D [0, 1] is defined by μ ¯ ( x ) = [ 1 - μ U ( x ) , 1 - μ L ( x ) ] , ∀ x ∈ V . Let A = { [ μ i L ( x ) , μ i U ( x ) ] ⊆ D [ 0 , 1 ] | x ∈ V , i ∈ Ω } be a set of all IVFSs in V, then

⋃ i ∈ Ω [ μ i L ( x ) , μ i U ( x ) ] = [ sup i ∈ Ω μ i L ( x ) , sup i ∈ Ω μ i U ( x ) ] ⋂ i ∈ Ω [ μ i L ( x ) , μ i U ( x ) ] = [ inf i ∈ Ω μ i L ( x ) , inf i ∈ Ω μ i U ( x ) ] , for all x ∈ V , By a cubic set (CS) in V we mean a structure A = { 〈 x , [ μ L ( x ) , μ U ( x ) ] , σ ( x ) 〉 | x ∈ V } , in which [μ ^L , μ ^U ] is an IVFS in V and σ is a FS in V. A CS A = {〈x, [μ ^L  (x) , μ ^U  (x)] , σ (x) 〉| x ∈ V} is simply denoted by A = 〈 [μ ^L , μ ^U ] , σ〉. A CS A in which [μ ^L  (x) , μ ^U  (x)] = [0, 0] and σ (x) =1 (resp. [μ ^L  (x) , μ ^U  (x)] = [1, 1] and σ (x) =0) for x ∈ V is denoted by 0 (resp. 1).

A CS A = 〈 [μ ^L , μ ^U ] , σ〉 in V is said to be an internal cubic set if μ ^L  (x) ≤ σ (x) ≤ μ ^U  (x), and said to an external cubic set if σ (x) ∉ [μ ^L , μ ^U ], for all x ∈ V.

The complement of A = 〈 [μ ^L , μ ^U ] , σ〉 is defined to be the CS A ¯ = { 〈 x , [ 1 - μ U ( x ) , 1 - μ L ( x ) ] , 1 - σ ( x ) 〉 | x ∈ V } . A graph is a pair G^* = (V, E), where V is a set of vertices of G^* and E is a set of edges of G^*. The set D ⊆ V is called a dominating set (DS) in G^* if, for every y ∈ V - D, there is some x ∈ D such that xy ∈ E. The minimum cardinality DSs in G^* is said the domination number of G^* and is denoted by γ.

An FG G = (φ, ψ) on underlying graph G^* = (V, E) consists of two FS φ and ψ on V and E, respectively, such that ψ ( x , y ) ≤ φ ( x ) ∧ φ ( y ) , ∀ ( x , y ) ∈ E . We call φ the fuzzy vertex function of V, and ψ the fuzzy edge function of E. Note that ψ is a symmetric fuzzy relation on φ. We use the notation xy for an element (x, y) ∈ E. The order of a FG is defined by p = ∑_x∈Vφ (x). The degree of a vertex x in G is defined by deg(x) = ∑_xy∈Eψ (xy).

Definition 2.1. [33] Let V≠ ∅ be a finite set. By a CG over V, we mean a pair G = ( A , B ) in which A = 〈 [ μ A L , μ A U ] , σ A 〉 is a CS in V and B = 〈 [ μ B L , μ B U ] , σ B 〉 is a CS in V × V such that for all xy ∈ V × V μ B L ( xy ) ≤ μ A L ( x ) ∧ μ A L ( y ) , μ B U ( xy ) ≤ μ A U ( x ) ∧ μ A U ( y ) , σ B ( xy ) ≤ σ A ( x ) ∧ σ A ( y ) . Let [ μ A * L , μ A * U ] = { x ∈ V | [ μ A L ( x ) , μ A U ( x ) ] > [ 0 , 0 ] } , σ A * = { x ∈ V | σ A ( x ) > 0 } , [ μ B * L , μ B * U ] = { xy ∈ V × V | [ μ B L ( xy ) , μ A U ( xy ) ] > [ 0 , 0 ] } , σ B * = { xy ∈ V × V | σ B ( xy ) > 0 } , and V * = [ μ A * L , μ A * U ] ∩ σ A * , E * = [ μ B * L , μ B * U ] ∩ σ B * . Then, G * = ( V * , E * ) is a underlying crisp graph of G .

Note:Although the cubic graph in graph theory is also referred to as 3-regular graphs, but the meaning of the CG throughout this article means a cubic fuzzy graph consisting of an IVFG and an FG.

Definition 2.2. [33] A CG G = ( A , B ) over V^* is said to be complete if for all xy ∈ V^* × V^* μ B L ( xy ) = μ A L ( x ) ∧ μ A L ( y ) , μ B U ( xy ) = μ A U ( x ) ∧ μ A U ( y ) , σ B ( xy ) = σ A ( x ) ∧ σ A ( y ) .

Definition 2.3. Let G = ( A , B ) be a CG. Then vertex cardinality and edge cardinality of G are defined by P = ∑ x ∈ V * ( 1 - μ A L ( x ) + μ A U ( x ) + σ A ( x ) 3 ) Q = ∑ xy ∈ E * ( 1 - μ B L ( xy ) + μ B U ( xy ) + σ B ( xy ) 3 ) .

Definition 2.4. Let G = ( A , B ) be a CG and S ⊆ V. Then cardinality of S is defined by | S | = ∑ x ∈ S ( 1 - μ A L ( x ) + μ A U ( x ) + σ A ( x ) 3 ) .

Definition 2.5. [33] Let G = ( A , B ) be a CG over V^*. A cubic path in G is a sequence P _c  : x₁x₂ ⋯ x _r of distinct vertics of V such that [ μ B L ( x c - 1 x c ) , μ B U ( x c - 1 x c ) ] > ] 0 , 0 ] and σ _B  (x_c-1x _c ) >0 for c = 1, 2, ⋯ , r. We say that r is the length of the cubic path P _c , and P _c  : x₁x₂ ⋯ x _r is a cubic path between x₀ and x _r .

The strength of P _c is defined by S ( P c ) = 〈 ⋂ i = 1 r [ μ B L ( x i - 1 x i ) , μ B U ( x i - 1 x i ) ] , ⋀ i = 1 r σ B ( x i - 1 x i ) 〉 . The strength of connectedness between vertex x and vertex y is denoted by 〈 [ μ B ∞ L ( xy ) , μ B ∞ U ( xy ) ] , σ B ∞ ( xy ) 〉 and it is the maximum of the strengths of all cubic paths between x and y.

Definition 2.6. Let G = ( A , B ) be a CG on V^*. Then an edge xy ∈ E^* is said to be cubic strong edge in G if μ B L ( xy ) ≥ μ B ∞ L ( xy ) , μ B U ( xy ) ≥ μ B ∞ U ( xy ) , σ B ( xy ) ≥ σ B ∞ ( xy ) . If every xy ∈ E^* be strong, then G is said to be strong.

In this section, we define DS in a CG and examine some of its properties.

Definition 3.1. Let G = ( A , B ) be a CG over V^* and x, y ∈ V^*, then x dominates y, if there exists a cubic strong edge between x and y.

Definition 3.2. Let G = ( A , B ) be a CG over V^*. S ⊆ V^* is called a DS in G if for every y ∉ S, there exists x ∈ S such that x dominates y. The minimum cardinality of all DSs in G is called the domination number of G and denoted by γ ( G ) or by simply γ. In this case, S is called a γ-set.

Example 3.3. Consider a CG G = ( A , B ) as shown in Figure 1.

OPEN IN VIEWER

Fig. 1

CG G = ( A , B ) .

All edges are strong except ab and bd. The DSs for Figure 1 are as follows: S 1 = { a , c } , S 2 = { b , e } , S 3 = { c , e } , S 4 = { a , b } , S 5 = { b , d } . After calculating the cardinality of S₁, S₂, S₃, S₄, S₅, we obtain | S 1 | = 1.2 , | S 2 | = 1.36 , | S 3 | = 1.33 , | S 4 | = 1.23 , | S 5 | = 1.13 . It is clear that S₅ has the minimum cardinality among other DSs. So, γ = 1.13.

Definition 3.4. A DS S of CG G is called minimal DS if for every vertex x ∈ S, the set S - {x} is not a DS, i.e., no proper subset of S is a DS of G .

Remark 3.5. The domination is a symmetric relation an V^*.

Definition 3.6. Let G = ( A , B ) be a CG. A cubic strong neighbor of x, is defined as: N ( x ) = { y ∈ V | xy is a cubic strong edge } . Furthermore, N [ x ] = N ( x ) ∪ { x } is called a closed cubic strong neighbor of x. For non-empty set of S, we have N ( S ) = { N ( x ) | x ∈ S } , N [ S ] = N ( S ) ∪ S .

Definition 3.7. The cubic strong neighborhood degree of vertex x is defined as: D N ( x ) = 〈 [ ∑ w ∈ N ( x ) μ L ( w ) , ∑ w ∈ N ( x ) μ U ( w ) ] , ∑ w ∈ N ( x ) σ ( w ) 〉 , and the minimum and maximum cardinality cubic strong neighborhood of G are denoted by δ N and Δ N , respectively.

Example 3.8. Let G = ( A , B ) be a CG as shown in Figure 2. All edges are strong. We have

N ( a ) = { d } , N ( b ) = { c , d } , N ( c ) = { b , d } , N ( d ) = { a , b , c } . Thus, D N ( a ) = 〈 [ 0.5 , 0.9 ] , 0.3 〉 , D N ( b ) = 〈 [ 0.6 , 1.3 ] , 0.7 〉 , D N ( c ) = 〈 [ 0.8 , 1.5 ] , 0.9 〉 , D N ( d ) = 〈 [ 0.8 , 1.7 ] , 1.7 〉 . So, δ N = | 〈 [ 0.5 , 0.9 ] , 0.3 〉 | = 0.57 , and Δ N = | 〈 [ 0.8 , 1.7 ] , 1.7 〉 | = 1.2 .

OPEN IN VIEWER

Fig. 2

A strong CG.

Definition 3.9. In a CG G = ( A , B ) , a vertex x ∈ V is called an isolated vertex if N ( x ) = ∅ , i.e., for any y ∈ V where x ≠ y, xy is not a cubic strong edge.

Theorem 3.10. If G = ( A , B ) be a CG without isolated vertices and S is the minimal DS in G , then V - S is a DS.

Proof. Since G has no isolated vertex, so every vertex x ∈ V must be dominated by at least one vertex in S - {x}. This is in contradiction with the minimality of S. Hence, V - S is a DS. □

Theorem 3.11. A DS S of a CG G = ( A , B ) is a minimal DS if and only if for each z ∈ S one of the following two conditions holds.

i ) N ( z ) ∩ S = ∅ .

ii) There is a vertex w ∈ V^* - S such that N ( w ) ∩ S = { z } .

Proof. Let S be a minimal DS of G . Then, for every vertex z ∈ S, S - {z} is not a DS and there exists w ∈ V^* - (S - {z}) which is not dominated by any vertex in S - {z}. If w = z, then (i) holds.

If w ≠ z, then w is not dominated by S - {z}, but is dominated by S, i.e., w is dominated only by z in S. Thus, N ( w ) ∩ S = { z }

Conversely, let S be a DS and for every vertex z ∈ S, one of two conditions holds. Suppose S be not a minimal DS. Then there exists a vertex z ∈ S such that S - {z} is a DS. Therefore, z is dominated by at least on vertex in S - {z} which implies that the condition (ii) does not hold. This is a contradiction. Thus S must be a minimal DS. □

Corollary 3.12. If G = ( A , B ) be a CG without isolated vertex, then γ ≤ P 2 .

Proof. Let S be a minimal DS of G . So, V^* - S is a DS too. Since P = |V^*| = |S| + |V^* - S|, at least one of the sets S or V^* - S, has the cardinality less than or equal P 2 .

Theorem 3.13. If G = ( A , B ) be CG without isolated vertex, then γ ≤ P - Δ N and γ ≤ P - δ N .

Proof. Let u be a vertex in CG G = ( A , B ) . Assume that D N ( u ) = Δ N . Let V * - N ( u ) is a DS of G so that γ ≤ | V * - N ( u ) | = P - Δ N . Similarly, since δ N ≤ Δ N . Hence, γ ≤ P - δ N . □

Definition 3.14. Two vertices in a CG are said to be independent if there is no cubic strong edge between them. A subset F ⊆ V^* is said to be independent cubic set (ICS) if μ B L ( xy ) < μ A L ( x ) ∧ μ A L ( y ) μ B U ( xy ) < μ A U ( x ) ∧ μ A U ( y ) σ B ( xy ) < σ A ( x ) ∧ σ A L ( y ) , for all x , y ∈ F . A ICS F is said to be maximal if for every w ∈ V^* - F, F ∪ {w} is not a ICS.

Theorem 3.15. A ICS is a maximal ICS of CG G = ( A , B ) if and only if it is both ICS and DS.

Proof. Let F be a maximal ICS in a CG. So, for every vertex z ∈ V^* - F, the set F ∪ {z} is not independent. For every vertex z ∈ V^* - F, there is a vertex t ∈ F such that t is a strong neighbor to z. So, F is a DS. Hence, F is both DS and ICS.

Conversely, assume F is both ICS and DS. Suppose F is not maximal ICS, then there exists a vertex z ∈ V^* - F, the set F ∪ {z} is ICS. If F ∪ {z} is ICS, then no vertex in F is strong neighbor to z. Hence, F can not be a DS, which is a contradiction. Hence, F is a maximal ICS. □

Theorem 3.16. Every maximal ICS in a CG G = ( A , B ) is a minimal DS.

Proof. Let F be a maximal ICS in a CG. By Theorem 3.15, F is a DS. Suppose F is not a minimal DS, then there exists at least one vertex z ∈ F for which F - {z} is a DS. But if F - {z} dominates V^* - (F - {z}), then at least one vertex in F - {z} must be strong neighbor to z. This is contradiction. So, F must be a minimal DS. □

Definition 3.17. A DS S in a CG G = ( A , B ) is said to be independent dominating set (IDS) in G if S is ICS.

An IDS S in a CG G is said to be maximal IDS, if for every z ∈ V^* - S, the set S ∪ {z} is not IDS. The minimum cardinality among all maximal IDSs is called lower independent dominating number of G , and it is denoted by γ i ( G ) or simply γ _i .

The maximum cardinality among all maximal IDSs is called upper independent dominating number of G , and it is denoted by Γ i ( G ) or simply Γ _i .

Example 3.18. The IDSs in Figure 2, are S₁ = {a, b} and S₂ = {a, c}. S₂ is maximal IDS of minimum cardinality γ _i  = 1.24, and S₁ is a maximal IDS of maximum cardinality Γ _i  = 1.3.

Remark 3.19. If G be a CG, then γ ≤ γ _i  .

Theorem 3.20. Let S be a γ-set of a CG. If the subgraph 〈S〉 induced by S has isolated vertices, then γ = γ _i .

Proof. Since S is a γ-set of a CG, So, S is a DS. Suppose that the subgraph 〈S〉 induced by S has isolated vertices. Hence, all vertices of S are independent. Thus, γ = γ _i .□

Corollary 3.21. If G = ( A , B ) be a complete-CG, then γ = γ _i .

Theorem 3.22. Let G = ( A , B ) be a connected-CG without isolated vertices. If G^* is not cycle or does not have an induced cycle subgraph, then γ ≤ P - Γ i ≤ P - γ i .

Proof. Let G be a connected-CG without isolated vertices, such that G * is not a cycle and S be a maximal ICS in G . Then V^* - S is a DS in G . Hence, γ ≤ | V * - S | = P - Γ i . Similarly, since γ _i  ≤ Γ _i . Hence, γ ≤ P - γ _i .□

In this section, we examine the domination of operations in CG.

Definition 4.1. Let G 1 = ( A 1 , B 1 ) and G 2 = ( A 2 , B 2 ) be two CGs of the underlying graphs G 1 * and G 2 * , respectively. The cartesian product of G 1 and G 2 is denoted by G 1 × G 2 = ( A 1 × A 2 , B 1 × B 2 ) and is defined as follows:

( i ) { [ μ A 1 L × μ A 2 L , μ A 1 U × μ A 2 U ] ( x 1 , x 2 ) = [ μ A 1 L ( x 1 ) ∧ μ A 2 L ( x 2 ) , μ A 1 U ( x 1 ) ∧ μ A 2 U ( x 2 ) ] , ( σ A 1 × σ A 2 ) ( x 1 , x 2 ) = σ A 1 ( x 1 ) ∧ σ A 2 ( x 2 ) , ∀ ( x 1 , x 2 ) ∈ V * = V 1 * × V 2 * . ( ii ) { [ μ B 1 L × μ B 2 L , μ B 1 U × μ B 2 U ] ( ( x 1 , x 2 ) ( x 1 , y 2 ) ) = [ μ A 1 L ( x 1 ) ∧ μ B 2 L ( x 2 y 2 ) , μ A 1 U ( x 1 ) ∧ μ B 2 U ( x 2 y 2 ) ] , ( σ B 1 × σ B 2 ) ( ( x 1 , x 2 ) ( x 1 , y 2 ) ) = σ A 1 ( x 1 ) ∧ σ B 2 ( x 2 y 2 ) , ∀ x 1 ∈ V 1 * , x 2 y 2 ∈ E 2 * . ( iii ) { [ μ B 1 L × μ B 2 L , μ B 1 U × μ B 2 U ] ( ( x 1 , x 2 ) ( y 1 , x 2 ) ) = [ μ B 1 L ( x 1 y 1 ) ∧ μ A 2 L ( x 2 ) , μ B 1 U ( x 1 y 1 ) ∧ μ A 2 U ( x 2 ) ] , ( σ B 1 × σ B 2 ) ( ( x 1 , x 2 ) ( y 1 , x 2 ) ) = σ B 1 ( x 1 y 1 ) ∧ σ A 2 ( x 2 ) , ∀ x 2 ∈ V 2 * , x 1 y 1 ∈ E 1 * .

Example 4.2. Consider two CGs G 1 = ( A 1 , B 1 ) and G 2 = ( A 2 , B 2 ) as shown in Figure 3. The cartesian product of the CGs G 1 and G 2 is shown in Figure 4.

OPEN IN VIEWER

Fig. 3

CGs G 1 and G 2 .

OPEN IN VIEWER

Fig. 4

CG G 1 × G 2 .

Remark 4.3. If a vertex x₁ dominates a vertex y₁ in G 1 and a vertex x₂ dominates a vertex y₂ in G 2 , then the avertex (x₁, x₂) dominates the vertex x₁y₂ as shown in Figure 4.

Theorem 4.4. Let G 1 = ( A 1 , B 1 ) and G 2 = ( A 2 , B 2 ) be CGs with DSs S₁ and S₂, respectively. Then V 1 * × S 2 and S 1 × V 2 * are DSs of G 1 × G 2 .

Proof. Let G 1 = ( A 1 , B 1 ) and G 2 = ( A 2 , B 2 ) be CGs with DSs S₁ and S₂, respectively. So. every vertex in G 1 and G 2 be dominated by a vertex in S₁ and S₂, respectively. Case (i): x ∈ V 1 * and x 2 y 2 ∈ E 2 * . If the edge x 2 y 2 ∈ E 2 * be cubic strong edge in G 2 , then ( μ B 1 L × μ B 2 L ) ( ( x 1 , x 2 ) ( x 1 , y 2 ) ) = μ A 1 L ( x 1 ) ∧ μ B 2 L ( x 2 y 2 ) = μ A 1 L ( x 1 ) ∧ μ A 2 L ( x 2 ) ∧ μ A 2 L ( y 2 ) = μ A 1 L ( x 1 ) ∧ μ A 2 L ( x 2 ) ∧ μ A 1 L ( x 1 ) ∧ μ A 2 L ( y 2 ) = ( μ A 1 L × μ A 2 L ) ( x 1 , x 2 ) ∧ ( μ A 1 L × μ A 2 L ) ( x 1 , y 2 ) . Similarly, ( μ B 1 U × μ B 2 U ) ( ( x 1 , x 2 ) ( x 1 , y 2 ) ) = ( μ A 1 U × μ A 2 U ) ( x 1 , x 2 ) ∧ ( μ A 1 U × μ A 2 U ) ( x 1 , y 2 ) . Also, ( σ B 1 × σ B 2 ) ( ( x 1 , x 2 ) ( x 1 , y 2 ) ) = σ A 1 ( x 1 ) ∧ σ B 2 ( x 2 y 2 ) = σ A 1 ( x 1 ) ∧ σ A 2 ( x 2 ) ∧ σ A 2 ( y 2 ) = σ A 1 ( x 1 ) ∧ σ A 2 ( x 2 ) ∧ σ A 1 ( x 1 ) ∧ σ A 2 ( y 2 ) = ( σ A 1 × σ A 2 ) ( x 1 , x 2 ) ∧ ( σ A 1 × σ A 2 ) ( x 1 , y 2 ) . This gives results that (x₁, x₂) (x₁, y₂) is a cubic strong edge in G 1 × G 2 whose end vertices belong to V 1 * × S 2 . Since x 2 y 2 ∈ E 2 * is a cubic strong edge such that x₂ ∈ S₂ or y₂ ∈ S₂. Hence, the set V 1 * × S 2 is dominated the all vertices in G 1 × G 2 .

case (ii): x 2 ∈ V 2 * , and x 1 y 1 ∈ E 1 * . If the edge x 1 y 1 ∈ E 1 * be cubic strong edge in G 1 , then ( μ B 1 L × μ B 2 L ) ( ( x 1 , x 2 ) ( y 1 , x 2 ) ) = μ B 1 L ( x 1 y 1 ) ∧ μ A 2 L ( x 2 ) = μ A 1 L ( x 1 ) ∧ μ A 1 L ( y 1 ) ∧ μ A 2 L ( x 2 ) = μ A 1 L ( x 1 ) ∧ μ A 2 L ( x 2 ) ∧ μ A 1 L ( y 1 ) ∧ μ A 2 L ( x 2 ) = ( μ A 1 L × μ A 2 L ) ( x 1 , x 2 ) ∧ ( μ A 1 L × μ A 2 L ) ( y 1 , x 2 ) .

Similarly, ( μ B 1 U × μ B 2 U ) ( ( x 1 , x 2 ) ( y 1 , x 2 ) ) = ( μ A 1 U × μ A 2 U ) ( x 1 , x 2 ) ∧ ( μ A 1 U × μ A 2 U ) ( y 1 , x 2 ) . Also, ( σ B 1 × σ B 2 ) ( ( x 1 , x 2 ) ( y 1 , x 2 ) ) = σ B 1 ( x 1 y 1 ) ∧ σ A 2 ( x 2 ) = σ A 1 ( x 1 ) ∧ σ A 1 ( y 1 ) ∧ σ A 2 ( x 2 ) = σ A 1 ( x 1 ) ∧ σ A 2 ( x 2 ) ∧ σ A 1 ( y 1 ) ∧ σ A 2 ( x 2 ) = ( σ A 1 × σ A 2 ) ( x 1 , x 2 ) ∧ ( σ A 1 × σ A 2 ) ( y 1 , x 2 ) . Therefore, (x₁, x₂) (y₁, x₂) is a cubic strong edge in G 1 × G 2 whose end vertices belong to S 1 × V 2 * . Since x 1 y 1 ∈ E 1 * is a cubic strong edge such that x₁ ∈ S₁ or y₁ ∈ S₁. So S 1 × V 2 * is DS in G 1 × G 2 .□

Corollary 4.5. If S₁ and S₂ are minimum DSs of CGs G 1 = ( A 1 , B 1 ) and G 2 = ( A 2 , B 2 ) respectively, then γ ( G 1 × G 2 ) ≤ | S 1 × V 2 * | ∧ | V 1 * × S 2 | .

Example 4.6. In Example 4.2, we have S 1 = { x 1 } , S 2 = { y 2 } , | S 1 × V 2 * | = 1.14 , | V 1 * × S 2 | = 1.10 , γ ( G 1 × G 2 ) = 1.10 . Clearly, 1.10 ≤ min {1.14, 1.10}.

Definition 4.7. Let G 1 = ( A 1 , B 1 ) and G 2 = ( A 2 , B 2 ) be two CGs of the underlying graphs G 1 * and G 2 * , respectively. The composition of G 1 and G 2 is denoted by G 1 ∘ G 2 = ( A 1 ∘ A 2 , B 1 ∘ B 2 ) and is defined as follows:

( i ) { [ μ A 1 L ∘ μ A 2 L , μ A 1 U ∘ μ A 2 U ] ( x 1 , x 2 ) = [ μ A 1 L ( x 1 ) ∧ μ A 2 L ( x 2 ) , μ A 1 U ( x 1 ) ∧ μ A 2 U ( x 2 ) ] ( σ A 1 ∘ σ A 2 ) ( x 1 , x 2 ) = σ A 1 ( x 1 ) ∧ σ A 2 ( x 2 ) ∀ ( x 1 , x 2 ) ∈ V * = V 1 * × V 2 * , ( ii ) { [ μ B 1 L ∘ μ B 2 L , μ B 1 U ∘ μ B 2 U ] ( ( x 1 , x 2 ) ( x 1 , y 2 ) ) = [ μ A 1 L ( x 1 ) ∧ μ B 2 L ( x 2 y 2 ) , μ A 1 U ( x 1 ) ∧ μ B 2 U ( x 2 y 2 ) ] ( σ B 1 ∘ σ B 2 ) ( ( x 1 , x 2 ) ( x 1 , y 2 ) ) = σ A 1 ( x 1 ) ∧ σ B 2 ( x 2 y 2 ) ∀ x 1 ∈ V 1 * , x 2 y 2 ∈ E 2 * , ( iii ) { [ μ B 1 L ∘ μ B 2 L , μ B 1 U ∘ μ B 2 U ] ( ( x 1 , x 2 ) ( y 1 , x 2 ) ) = [ μ B 1 L ( x 1 y 1 ) ∧ μ A 2 L ( x 2 ) , μ B 1 U ( x 1 y 1 ) ∧ μ A 2 U ( x 2 ) ] ( σ B 1 ∘ σ B 2 ) ( ( x 1 , x 2 ) ( y 1 , x 2 ) ) = σ B 1 ( x 1 y 1 ) ∧ σ A 2 ( x 2 ) ∀ x 2 ∈ V 2 * , x 1 y 1 ∈ E 1 * , ( iv ) { [ μ B 1 L ∘ μ B 2 L , μ B 1 U ∘ μ B 2 U ] ( ( y 1 , y 2 ) ( x 1 , x 2 ) ) = [ μ A 2 L ( y 2 ) ∧ μ A 2 L ( x 2 ) ∧ μ B 1 L ( x 1 y 1 ) , μ A 2 U ( y 1 ) ∧ μ A 2 U ( x 2 ) ∧ μ B 1 U ( x 1 y 1 ) ] ( σ B 1 ∘ σ B 2 ) ( ( y 1 , y 2 ) ( x 1 , x 2 ) ) = σ A 2 ( y 2 ) ∧ σ A 2 ( x 2 ) ∧ σ B 1 ( x 1 y 1 ) ∀ x 2 , y 2 ∈ V 2 * , x 2 ≠ y 2 , x 1 y 1 ∈ E 1 * .

Theorem 4.8. Let S₁ and S₂ be DSs of the CGs G 1 = ( A 1 , B 1 ) and G 2 = ( A 2 , B 2 ) , respectively. Then, S₁ × S₂ is a DS of G 1 ∘ G 2 .

Proof. Let (x, y) ∉ S₁ × S₂, Then x ∉ S₁ or y ∉ S₂.

Case (i): x ∉ S₁ and y ∈ S₂. Let x₁ ∈ S₁ dominates x. So, μ B 1 L ( xx 1 ) = μ A 1 L ( x ) ∧ μ A 1 L ( x 1 ) , μ B 1 U ( xx 1 ) = μ A 1 U ( x ) ∧ μ A 1 U ( x 1 ) , σ B 1 ( xx 1 ) = σ A 1 ( x ) ∧ σ A 1 ( x 1 ) . Therefore, (x₁, y) ∈ S₁ × S₂ and we have ( μ B 1 L ∘ μ B 2 L ) ( ( x , y ) ( x 1 , y ) ) = μ B 1 L ( xx 1 ) ∧ μ A 2 L ( y ) = μ A 1 L ( x ) ∧ μ A 1 L ( x 1 ) ∧ μ A 2 L ( y ) = μ A 1 L ( x ) ∧ μ A 2 L ( y ) ∧ μ A 1 L ( x 1 ) ∧ μ A 2 L ( y ) = ( μ A 1 L ∘ μ A 2 L ) ( x , y ) ∧ ( μ A 1 L ∘ μ A 2 L ) ( x 1 , y ) . Similarly, ( μ B 1 U ∘ μ B 2 U ) ( ( x , y ) ( x 1 , y ) ) = ( μ A 1 U ∘ μ A 2 U ) ( x , y ) ∧ ( μ A 1 U ∘ μ A 2 U ) ( x 1 , y ) . Also, ( σ B 1 ∘ σ B 2 ) ( ( x , y ) ( x 1 , y ) ) = σ B 1 ( xx 1 ) ∧ σ A 2 ( y ) = σ A 1 ( x ) ∧ σ A 1 ( x 1 ) ∧ σ A 2 ( y ) = σ A 1 ( x ) ∧ σ A 2 ( y ) ∧ σ A 1 ( x 1 ) ∧ σ A 2 ( y ) = ( σ A 1 ∘ σ A 2 ) ( x , y ) ∧ ( σ A 1 ∘ σ A 2 ) ( x 1 , y ) . Thus, (x₁, y) dominates (x, y) in G 1 ∘ G 2 .

Case (ii): x ∈ S₁ and y ∉ S₂. Let y₁ ∈ S₂ dominates y. Then, (x, y₁) ∈ S₁ × S₂ and

( μ B 1 L ∘ μ B 2 L ) ( ( x , y ) ( x , y 1 ) ) = μ A 1 L ( x ) ∧ μ B 2 L ( yy 1 ) = μ A 1 L ( x ) ∧ μ A 2 L ( y ) ∧ μ A 2 L ( y 1 ) = μ A 1 L ( x ) ∧ μ A 2 L ( y ) ∧ μ A 1 L ( x ) ∧ μ A 2 L ( y 1 ) = ( μ A 1 L ∘ μ A 2 L ) ( x , y ) ∧ ( μ A 1 L ∘ μ A 2 L ) ( x , y 1 ) . Similarly, ( μ B 1 U ∘ μ B 2 U ) ( ( x , y ) ( x , y 1 ) ) = ( μ A 1 U ∘ μ A 2 U ) ( x , y ) ∧ ( μ A 1 U ∘ μ A 2 U ) ( x , y 1 ) . ( σ B 1 ∘ σ B 2 ) ( ( x , y ) ( x 1 , y ) ) = σ A 1 ( x ) ∧ σ B 2 ( yy 1 ) = σ A 1 ( x ) ∧ σ A 2 ( y ) ∧ σ A 2 ( y 1 ) = σ A 1 ( x ) ∧ σ A 2 ( y ) ∧ σ A 1 ( x ) ∧ σ A 2 ( y 1 ) = ( σ A 1 ∘ σ A 2 ) ( x , y ) ∧ ( σ A 1 ∘ σ A 2 ) ( x , y 1 ) . Thus, (x, y₁) dominates (x, y) in G 1 ∘ G 2 .

Case (iii): x ∉ S₁ and y ∉ S₂. Let x₁ ∈ S₁, y₁ ∈ S₂ such that x₁ dominates x in G 1 and y₁ dominates y in G 2 . Then, (x₁, y₁) ∈ S₁ × S₂. We have ( μ B 1 L ∘ μ B 2 L ) ( ( x , y ) ( x 1 , y 1 ) ) = μ A 2 L ( y ) ∧ μ A 2 L ( y 1 ) ∧ μ B 1 L ( xx 1 ) = μ A 2 L ( y ) ∧ μ A 2 L ( y 1 ) ∧ μ A 1 L ( x ) ∧ μ A 1 L ( x 1 ) = ( μ A 1 L ∘ μ A 2 L ) ( x , y ) ∧ ( μ A 1 L ∘ μ A 2 L ) ( x 1 , y 1 ) . Similarly, ( μ B 1 U ∘ μ B 2 U ) ( ( x , y ) ( x 1 , y 1 ) ) = ( μ A 1 U ∘ μ A 2 U ) ( x , y ) ∧ ( μ A 1 U ∘ μ A 2 U ) ( x 1 , y 1 ) . ( σ B 1 ∘ σ B 2 ) ( ( x , y ) ( x 1 , y ) ) = σ A 2 ( y ) ∧ σ A 2 ( y 1 ) ∧ σ B 1 ( xx 1 ) = σ A 2 ( y ) ∧ σ A 2 ( y 1 ) ∧ σ A 1 ( x ) ∧ σ A 1 ( x 1 ) = ( σ A 1 ∘ σ A 2 ) ( x , y ) ∧ ( σ A 1 ∘ σ A 2 ) ( x 1 , y 1 ) . Thus, (x₁, y₁) dominates (x, y) in G 1 ∘ G 2 . Therefore, S₁ × S₂ is a DS of G 1 ∘ G 2 . □