# Graphical Analysis of Covering and Paired Domination in the Environment of Neutrosophic Information

Authors: Sami Ullah Khan; Abdul Nasir; Naeem Jan; Zhen-Hua Ma
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

Neutrosophic graph (NG) is a powerful tool in graph theory, which is capable of modeling many real-life problems with uncertainty due to unclear, varying, and indeterminate information. Meanwhile, the fuzzy graphs (FGs) and intuitionistic fuzzy graphs (IFGs) may not handle these problems as efficiently as NGs. It is difficult to model uncertainty due to imprecise information and vagueness in real-world scenarios. Many real-life optimization problems are modeled and solved using the well-known fuzzy graph theory. The concepts of covering, matching, and paired domination play a major role in theoretical and applied neutrosophic environments of graph theory. Henceforth, the current study covers this void by introducing the notions of covering, matching, and paired domination in single-valued neutrosophic graph (SVNG) using the strong edges. Also, many attention-grabbing properties of these concepts are studied. Moreover, the strong covering number, strong matching number, and the strong paired domination number of complete SVNG, complete single-valued neutrosophic cycle (SVNC), and complete bipartite SVNG are worked out along with their fascinating properties.


---

## Body

## 1. Introduction

There are several techniques and methods to model real-life events. But, in practicality, the information is sometimes uncertain, unclear, varying, and indeterminate, which is difficult to model using usual methods. Different theories are proposed for modeling uncertainty. Smarandache [1] gave a novel concept of expressing and solving uncertainty. He initiated the neutrosophic sets (NSs), which are the extensions of fuzzy sets (FSs) and intuitionistic fuzzy sets (IFSs). FSs proposed by Zadeh [2] and their generalizations are used to model the uncertainty. FSs involve the membership grade for each object whose value lies in the unit interval [0, 1]. The concept of IFSs was proposed and introduced by Atanassov in 1983 [3–5]. These are the generalization of FSs. The extension in IFSs is that in these sets the members of IFSs are assigned the membership grade as well as the nonmembership grade, provided that the sum of both grades lies in the unit interval [0, 1]. Atanassov also discussed the types, properties, and applications of IFSs. But these concepts are unable to model many real-life problems, so Smarandache [6] devised the notion of NSs that can deal with such problems. In NS, the object carries three independent grades: membership, abstinence, and nonmembership. Each of these grades lies in nonstandard unit interval ]−0, 1+[ and their sum lies in nonstandard interval ]−0, 3+[. Later the concept of single-valued neutrosophic set (SVNS) was introduced by Wang et al. [7], which is the subclass of NSs. This is even more practical and applies to a wide range of problems.Graph theory is one of the major branches of mathematics and combinatorics. It has many applications in numerous fields such as computer science, networking, geometry, algebra, set theory, economics, medicine, engineering, and chemistry. Hence, it has a wide range of applications in real world. Cantor presented the notion of crisp graphs, which uses the concepts of classical set theory. These graphs cannot model the problems associated with uncertainty because, in crisp graph, there are only two possibilities for a vertex and an edge, that is, whether it belongs to the graph or does not. In other words, it only conveys that the objects are related or not but does not indicate the strength and weakness of the relationship. So, an extension of crisp graphs is a fuzzy graph (FG), which was introduced by Rosenfeld in 1975 [8]. The idea of fuzziness in graph theory was given by Kauffman [9] in 1973 by using the fuzzy relations. Rosenfeld [8] further introduced the concepts related to FG such as connectedness, paths, cycles, trees, and bridges. Moreover, he also described some of the properties of FGs. Later on, the work of Rosenfeld was extended by many researchers who discussed its types, properties, and applications in real life, such as regular fuzzy graphs [10], fuzzy tolerance graphs [11], bipolar fuzzy graphs [12–14], interval-valued fuzzy graphs, balanced interval-valued fuzzy graphs [15, 16], fuzzy planar graphs [17, 18], bipolar fuzzy hypergraphs [19, 20], and completeness and regularity of generalized fuzzy graphs [21].One of the generalizations of FGs is intuitionistic fuzzy graph (IFG). The notion of IFG was presented by Shannon and Atanassov who also developed the idea of IFS relation, which was used in defining the IFGs [22]. They also discussed the many properties, theorems, and proofs regarding IFSs and IFGs. The work of Atanassov and Shannon was extended by many researchers who presented its properties, types, and applications; for example, join, union, and product of two IFGs were defined by Parvathi et al., and strong products, direct products, and lexicographic products of two IFGs were presented by Rashmanlou et al. The concepts of strong IFGs and intuitionistic fuzzy hypergraphs along with their applications were discussed by Akram and Davvaz [23, 24]. Karunambigai et al. discussed the balanced intuitionistic fuzzy graphs [25], covering and paired domination in IFGs [26], and intuitionistic fuzzy tolerance graph along with its applications was discussed by Sahoo and Pal [27, 28]. Even though the FGS and IFGs are great tools to model real-world problems, some of the problems with uncertain, indeterminate, and varying information cannot be handled by FGs and IFGs. Therefore, some more efficient tool was required to tackle such problems, and this requirement led to the idea of NSs and NGs.FSs and FGs discuss only the membership grades of the objects, while IFSs and IFGs discuss both the membership and nonmembership grades of an object, which do not totally model the human opinions, as human opinion can also be abstentious. Moreover, in IFSs and IFGs, the membership and nonmembership grades cannot be chosen independently. Their sum must be restricted to be in the unit interval. Therefore, this void created the space for the introduction of NSs and NGs. Smarandache, after initiating the concept of NSs, proposed four main categories of NGs: I-vertex NG and I-edge NG are based on literal indeterminacy (I), while (t, I, f)-vertex NG and (t, I, f)-edge NG are based on (t, I, f) components [29–33]. In NSs and NGs, the membership, abstinence, and nonmembership grades can be chosen independently from the unit interval, which provides comfort and ease to a decision-maker. Lately, NGs caught the attention of many researchers [34–40]. In addition, Garg [41–43] introduced aggregation operators and multiple decision-making techniques via SVNSs.This study focuses on the concepts of SVNGs, which were initiated by Broumi and Smarandache by applying the concept of SVNS to graphs [44]. They also discussed different types of SVNGs, bipolar SVNGs [45], grade, order, and size [46] and investigated many properties with proofs and examples. Recently, some researchers have worked on SVNGs, for instance, operations on SVNGs presented by Akram and Shahzadi [47], applications of operations on SVNGs given by Naz et al. [36], and properties of SVNGs discussed by Karaaslan and Davvaz [48].Since the domain of SVNG is greater than that of FGs and IFGs, it expands the range of applications of graphs. Like all other graphs, SVNGs also model the relations. So, it is applied to all sorts of problems consisting of relationships. It is capable of modeling the problems with uncertain and varying information in real world, where FGs and IFGs fail. This article introduces the notions of covering, matching, and paired domination in SVNG, complete SVNGs, and complete bipartite SVNGs. Moreover, strong coverings, that is, strong vertex cover and strong edge cover, the strong vertex covering number, and strong edge covering numbers are defined using the strong edge. In addition, the strong independent sets, the strong independent number, strong matching, and strong matching number are also discussed along with some interesting properties, theorems, proofs, and examples. The paired domination in SVNGs is also explained with examples and theorems.The paper is organized as follows: Section2 reviews some basic definitions and examples of FGs, IFSs, IFRs, IFGs, SVNSs, SVNRs, and SVNGs. Section 3 defines the strong covering of vertices and edges, strong independent sets (SIS), and strong matchings (SM) using strong edges (SEs) along with suitable examples and several interesting properties. Section 4 introduces the paired domination (PD), strong paired domination (SPD), and perfect paired domination. Finally, the research is concluded in Section 5.


## 2. Preliminaries

This section recalls some basic definitions of fuzzy graph (FG), intuitionistic fuzzy set (IFS), intuitionistic fuzzy relation (IFR), intuitionistic fuzzy graph (IFG), single-valued neutrosophic set (SVNS), single-valued neutrosophic relation (SVNR), and single-valued neutrosophic graph (SVNG). In addition, the examples of graphs are also given for better understanding.Definition 1.
(see [8]). A pair G=V,E is said to be an FG, where V is an FS in universe Ẍ defined as V=v1,v2,v3,…,vn and called the collection of vertices possessing the grade of membership m1:V⟶0,1 and the collection E on Ẍ is defined as
E⊆V×V=vi,vj|vi,vj∈V,i,j=1,2,3,…,n and called the collection of edges possessing the grade of membership m2:V×V⟶0,1, such that(1)m2vi,vj≤minm1vi,m1vj,∀vi,vj∈V,vi,vj∈E.Example 1.
An illustration of an FGG=V,E is given in Figure 1. Here, the collections of vertices and edges are V=v1,v2,v3,v4,v5 and E=v1,v2,v1,v3,v1,v4,v1,v5,v2,v3,v2,v4,v2,v5,v3,v4,v3,v5,v4,v5, respectively.Figure 1
Fuzzy graph.Definition 2.
(see [3]). A nonempty collection A in universe Ẍ of the following form is called an IFS:(2)A=<mx¨,nx¨>,x¨∈A,where the mapping m:A⟶0,1 represents the grade of membership and the mapping n:A⟶0,1 represents the nonmembership of A, such that(3)mx¨+nx¨∈0,1.Definition 3.
(see [3]). Let A1=m1,n1 and A2=m2,n2 be two IFSs such that m1:A1⟶0,1 and n1:A1⟶0,1 are mappings representing the membership and nonmembership grades of A1, respectively, and m2:A2⟶0,1 and n2:A2⟶0,1 are mappings representing the membership and nonmembership grades of A2, respectively; then the intuitionistic fuzzy relation (IFR) denoted by Ṝ is a collection of the form(4)R¯˙=A1×A2=<x¨,y¨,mx¨,y¨,nx¨,y¨>|x¨∈A1,y¨∈A2.
The mappingm:A1×A2⟶0,1 represents the membership grade and the mapping n:A1×A2⟶0,1 represents the nonmembership grade of R¯˙, where(5)mx¨,y¨≤minm1x¨,m1y¨,nx¨,y¨≤maxn1x¨,n1y¨.
This is provided thatmx¨,y¨+nx¨,y¨∈0,1.Definition 4.
(see [22]). An IFG is a pair G=V,E, where V is an IFS in universe Ẍ defined as
V=v1,v2,v3,…,vn and called the collection of vertices possessing the membership grade m1:V⟶0,1 and nonmembership grade n1:V⟶0,1, such that(6)m1vi+n1vi∈0,1,∀vi∈V,and the collection E on Ẍ is defined as E⊆V×V=vi,vj|vi,vj∈V,i,j=1,2,3,…,n and called the collection of edges possessing the membership grade m2:V×V⟶0,1 and the nonmembership grade n2:V×V⟶0,1, such that(7)m2vi,vj≤minm1vi,m1vj,n2vi,vj≤maxn1vi,n1vj.
This is provided thatm2vi,vj+n2vi,vj∈0,1,∀vi,vj∈E.Example 2.
In Figure2, the collection of vertices and the collection of edges for an IFG G are V=v1,v2,v3,v4 and E=v1,v2,v1,v3,v2,v4,v3,v4, respectively.Figure 2
Intuitionistic fuzzy graph.Definition 5.
(see [7]). A nonempty collection A in universe Ẍ of the following form is called an SVNS:(8)A=<mx¨,αx¨,nx¨>,x¨∈A,where the mapping m:A⟶0,1 represents the membership grade, α:A⟶0,1 represents the abstinence grade, and n:A⟶0,1 represents the nonmembership grade such that(9)mx¨+αx¨+nx¨∈0,3.Definition 6.
(see [46]). Let A1=m1,α1,n1 and A2=m2,α2,n2 be two SVNSs; then, A1 is said to be the SVNR on A2, if ∀x¨,y¨∈A1,(10)mx¨,y¨≤minm1x¨,m1y¨,αx¨,y¨≤minα1x¨,α1y¨,nx¨,y¨≤maxn1x¨,n1y¨.
This is provided thatmx¨,y¨+αx¨,y¨+nx¨,y¨∈0,3, where m1,α1, and n1 are the membership, abstinence, and nonmembership grades of A1, respectively, and m2,α2, and n2 are the membership, abstinence, and nonmembership grades of A2, respectively.Definition 7.
(see [44]). An SVNG is a pair G=V,E, where V is an SVNS in Ẍ defined as V=v1,v2,v3,…,vn and called the collection of vertices possessing the membership grade m1:V⟶0,1, abstinence grade α1:V⟶0,1, and nonmembership grade n1:V⟶0,1, such that(11)m1vi+α1vi+n1vi∈0,3,∀vi∈V,and E⊆V×V=vi,vj|vi,vj∈V,i,j=1,2,3,…,n is called the collection of edges possessing the membership grade m2:V×V⟶0,1, abstinence grade α2:V×V⟶0,1, and nonmembership grade n2:V×V⟶0,1, such that(12)m2vi,vj≤minm1vi,m1vj,α2vi,vj≤minα1vi,α1vj,n2vi,vj≤maxn1vi,n1vj.
This is provided thatm2vi,vj+α2vi,vj+n2vi,vj∈0,1,∀vi,vj∈E.Example 3.
An SVNGG=V,E is constructed in Figure 3 using the collection of vertices V=v1,v2,v3,v4 and the collection of edges E=v1,v2,v1,v3,v2,v4,v3,v4.Figure 3
Single-valued neutrosophic graph.


## 3. Covering and Matching in Single-Valued Neutrosophic Graphs

This section presents the definitions and examples of strong covering of vertices and edges, strong independent sets (SIS), and strong matchings (SM) using strong edges (SEs). Some interesting theorems are also proved for covering and matching in complete SVNG, SVNC, and complete bipartite SVNG.Definition 8.
LetG=V,E be an SVNG. A vertex and an SE incident to it are said to strongly cover each other. The collection of vertices Ṩ which covers all the SEs of an SVNG G is known as strong vertex cover (SVC) in G.M1S˙˙=∑u∈S˙˙m2u,v is the membership grade, M2S˙˙=∑u∈S˙˙α2u,v is the abstinence grade, and M3S˙˙=∑u∈S˙˙n2u,v is the nonmembership grade values of the SVC Ṩ, where m2u,v and α2u,v are the minimum of the membership and the abstinence values, respectively, and n2u,v is the maximum value among the collection of the nonmembership values of the strong edges incident on u. Let C10 and C20 denote the minimum values of membership and abstinence, and let C30 denote the maximum value of nonmembership of the SVC of G. Then the strong vertex covering number of G is defined and denoted by C0G=C0=C10,C20,C30. An SVC with minimum membership value, minimum abstinence value, and maximum nonmembership value in an SVNG G is said to be a minimum SVC.Theorem 1.
LetG=V,E be a complete SVNG; then, C10,C20, and C30 are defined as(13)C10=n−1m2u,v,C20=n−1α2u,v,C30=n−1n2u,v,where m2u,v is the membership value, α2u,v the abstinence value, and n2u,v is the nonmembership value of the weakest edge in G, and n is the number of vertices inG.Proof.
SinceG=V,E is a complete SVNG, each of its vertices is connected to every other vertex in G and all of its edges are strong. Hence, a strong cover vertex of G is formed by any collection of n−1 vertices. Let u be a minimum SVC, and u is connected to the vertices v1,v2,v3,…,vn−1. Then, the edges u,v1,u,v2,u,v3,…,u,vn−1 are all the weakest edges of G with m2u,v as the membership strength, α2u,v as the abstinence strength, and n2u,v as the nonmembership strength, where the collection S˙˙∈v1,v2,v3,…,vn−1 of n−1 vertices forms an SVC of G with(14)M1S˙˙=∑vi∈S˙˙m2u,vi,i=1,2,3,…,n−1,where m2u,vi is the minimum of the membership value of the SEs incident on vi. If the value of membership for the weakest edge of graph G is represented by m2u,v, then(15)C10=m2u,v+m2u,v+m2u,v+⋯+m2u,vn−1times.
Therefore,C10=n−1m2u,v.
Now,(16)M2S˙˙=∑vi∈S˙˙α2u,vi,i=1,2,3,…,n−1,where m2u,vi is the minimum of the abstinence value of the SE incident on vi. If the value of abstinence for the weakest edge of graph G is represented by α2u,v, then(17)C20=α2u,v+α2u,v+α2u,v+⋯+α2u,vn−1times.
Therefore,C20=n−1α2u,v.
In the same way,(18)M3S˙˙=∑vi∈S˙˙n2u,vi,i=1,2,3,…,n−1,where n2u,vi is the maximum of the nonmembership value of the SE incident on vi. If the value of abstinence for the weakest edge of graph G is represented by n2u,v, then(19)C30=n2u,v+n2u,v+n2u,v+⋯+n2u,vn−1times.
Therefore,C30=n−1n2u,v.Theorem 2.
IfK is a complete bipartite SVNG with V1 and V2 as partite sets, then(20)C10K=minM1V1,M1V2,C20K=minM2V1,M1V2,C30K=maxM3V1,M3V2.Proof.
SinceK is a complete bipartite SVNG, all of its edges are strong. Moreover, each of the vertices in V1 is connected to all the vertices in V2 and each of the vertices in V2 is connected to all the vertices of V1. The collection of all edges of K is the union of the collection of all edges incident to every vertex in V1 and the collection of all edges incident to each vertex in V2. Therefore, V1, V2, and V1∪V1 are the SVCs in K. It is obvious that(21)M1V1∪V2>M1V1,M1V1∪V2>M1V2.
Therefore,C10K=minM1V1,M1V2.
And,M2V1∪V2>M2V1 and M2V1∪V2>M2V2.
Therefore,C20K=minM2V1,M1V2.
Similarly,M3V1∪V2<M3V1 and M3V1∪V2>M3V2.
Therefore,C30K=maxM3V1,M3V2.Theorem 3.
IfG=V,E is a single-valued neutrosophic cycle (SVNC) and g¯ is a crisp cycle (CC), then(22)C10G=minM1S˙˙|S˙˙is an SVC inGwithS˙˙≥n2,C20G=minM2S˙˙|S˙˙is an SVC inGwithS˙˙≥n2,C30G=maxM3S˙˙|S˙˙is an SVC inGwithS˙˙≥n2.Proof.
As every edge in an SVNC is strong, the SVC number ofG is n/2, since the number of strong vertices in SVNG and the crisp cycle g¯ are the same because each edge is strong in both graphs [49]. Therefore, in the SVC of G,n/2 is the least number of vertices. So,(23)C10G=minM1S˙˙|S˙˙is an SVC inGwithS˙˙≥n2,C20G=minM2S˙˙|S˙˙is an SVC inGwithS˙˙≥n2,C30G=maxM3S˙˙|S˙˙is an SVC inGwithS˙˙≥n2.Definition 9.
Two vertices are said to be strongly independent in an SVNGG=V,E if they are not connected by an SE. If any collection in G contains any two strongly independent vertices, then such a collection is known as strong independent set (SIS).Definition 10.
LetS˙˙ be an SIS in an SVNG G=V,E. Then the values of membership, abstinence, and nonmembership of S˙˙ are defined as M1S˙˙=∑u∈S˙˙m2u,v, M2S˙˙=∑u∈S˙˙α2u,v, and M3S˙˙=∑u∈S˙˙n2u,v, respectively, where m2u,v and α2u,v represent the least value among the values of membership and the least value among the values of abstinence of the SEs incident on u. Similarly, the nonmembership value of S˙˙ is defined, where n2u,v represents the greatest value among the values of nonmembership of the SEs incident on u.
D0G=D0=D10,D20,D30 denotes and defines the strong independent number of an SVNG G=V,E, where D10andD20 are greatest values of membership and greatest values of abstinence of S˙˙ in G, respectively, and D30 is the least value of nonmembership of S˙˙ in G. The SIS with maximum membership value, maximum abstinence value, and minimum nonmembership value in an SVNG G is known as a maximum SIS of vertices.Theorem 4.
IfG=V,E is a complete SVNG, then D10=m2u,v, D20=α2u,v, and D30=n2u,v, where m2u,v, α2u,v, and n2u,v are the membership, abstinence, and nonmembership values of the weakest edge in G.Proof.
SinceG=V,E is a complete SVNG, each of its vertices is connected to every other vertex in G and all of its edges are strong. Therefore, there is only single SIS, that is, S˙˙=u. Hence, the result follows.Theorem 5.
IfK is a complete bipartite SVNG with V1 and V2 as partite sets, then(24)D10K=maxM1V1,M1V2,D20K=maxM2V1,M1V2,D30K=minM3V1,M3V2.Proof.
SinceK is a complete bipartite SVNG, all of its edges are strong. Moreover, each of the vertices in V1 is connected to all the vertices in V2, and each of the vertices in V2 is connected to all the vertices of V1. Therefore, V1 and V2 are the SISs in K. Hence,(25)D10K=maxM1V1,M1V2,D20K=maxM2V1,M1V2,D30K=minM3V1,M3V2.Theorem 6.
LetG=V,E be an SVNC and g¯ denotes a CC, then(26)D10G=maxM1S˙˙|S˙˙is an SVC inGwithS˙˙≤n2,D20G=maxM2S˙˙|S˙˙is an SVC inGwithS˙˙≤n2,D30G=minM3S˙˙|S˙˙is an SVC inGwithS˙˙≤n2.Proof.
As every edge in an SVNC is strong, the SVC number ofG is n/2, since the number of vertices in a SISs in g¯ and G are the same because each edge is strong in both graphs [49]. So, in the SVC of G,n/2 is the greatest number of vertices. Thus,(27)D10G=maxM1S˙˙|S˙˙is an SVC inGwithS˙˙≤n2,D20G=maxM2S˙˙|S˙˙is an SVC inGwithS˙˙≤n2,D30G=minM3S˙˙|S˙˙is an SVC inGwithS˙˙≤n2.Definition 11.
LetG=V,E be a connected SVNG. The collection Ṫ of SEs which covers all the vertices of an SVNG G is known as strong edge cover in G. M1T˙=∑u,v∈T˙m2u,v, M2T˙=∑u,v∈T˙α2u,v, and M3T˙=∑u,v∈T˙n2u,v are the membership, abstinence, and nonmembership values of SEC Ṫ, respectively. C1G=C1=C11,C21,C31 is the SEC number of an SVNG G, where C11 and C21 are the minimum membership and abstinence values of the SEC of SVNG G, whereas C31 is the greatest value of nonmembership. An SEC with minimum membership value, minimum abstinence value, and maximum nonmembership value in an SVNG G is said to be a minimum SEC.Theorem 7.
IfG=V,E is a complete SVNG, then(28)C11G=minM1T˙|T˙is an SEC inGwithT˙≥n2,C21G=minM2T˙|T˙is an SEC inGwithT˙≥n2,C31G=maxM3T˙|T˙is an SEC inGwithT˙≥n2.Proof.
As each of the vertices in a complete SVNGG is connected to every other vertex of G and all of its edges are strong, the SEC number of G is n/2, since each edge is strong in a complete SVNG and crisp graph; therefore, the numbers of strong edges in both graphs are the same [49]. Hence, the least number of edges in an SEC in G is n/2. Hence,(29)C11G=minM1T˙|T˙is an SEC inGwithT˙≥n2,C21G=minM2T˙|T˙is an SEC inGwithT˙≥n2,C31G=maxM3T˙|T˙is an SEC inGwithT˙≥n2.Theorem 8.
IfK is a complete bipartite SVNG with V1 and V2 as partite sets, then(30)C11K=minM1T˙|T˙is an SEC inKwithT˙≥maxV1,V2,C21K=minM2T˙|T˙is an SEC inKwithT˙≥maxV1,V2,C31K=maxM3T˙|T˙is an SEC inKwithT˙≥maxV1,V2.Proof.
SinceK is complete bipartite SVNG, all of its edges are strong. Moreover, each of the vertices in V1 is connected to all the vertices in V2 and vice versa. The edge covering number of K is V1,V2, since each edge is strong in a complete bipartite SVNG and g¯; therefore, the number of SEs in both graphs is the same [49]. Hence, the least number of edges in the SEC in K is V1,V2. Thus,(31)C11K=minM1T˙|T˙is an SEC inKwithT˙≥maxV1,V2,C21K=minM2T˙|T˙is an SEC inKwithT˙≥maxV1,V2,C31K=maxM3T˙|T˙is an SEC inKwithT˙≥maxV1,V2.Theorem 9.
LetG=V,E be an SVNC and g¯ is a CC, then(32)C11G=minM1T˙|T˙is an SEC inKwithT˙≥n2,C21G=minM2T˙|T˙is an SEC inKwithT˙≥n2,C31G=maxM3T˙|T˙is an SEC inKwithT˙≥n2.Proof.
Since every edge in an SVNC is strong, the SEC number ofG is n/2, as the number of SEs in SVNG and the crisp cycle g¯ are the same because each edge is strong in both graphs [49]. So, in the SEC of G, n/2 is the least number of edges. Thus,(33)C11G=minM1T˙|T˙is an SEC inKwithT˙≥n2,C21G=minM2T˙|T˙is an SEC inKwithT˙≥n2,C31G=maxM3T˙|T˙is an SEC inKwithT˙≥n2.Definition 12.
A collection of SEs denoted byṎ in an SVNG G=V,E is said to be an SIS of edges if all of its edges do not share a vertex. Ṏ is also known as strong matching (SM) in G=V,E.Definition 13.
Ifu,v∈O˜¨, where O˜¨ is an SM in an SVNG G=V,E, then it is said that u is strongly matched to v by O˜¨. M1O˜¨=∑u,v∈O˜¨m2u,v, M2O˜¨=∑u,v∈O˜¨α2u,v, and M3O˜¨=∑u,v∈O˜¨n2u,v are the membership, abstinence, and nonmembership values of the SEC O˜¨, respectively.
C1G=C1=C11,C21,C31 is the strong edge independent number or SM number of an SVNG G, where C11 and C21 are the maximum membership and abstinence values of the SMs of G, and C31 denotes the minimum nonmembership value. An SM with maximum membership value, maximum abstinence value, and minimum nonmembership value in an SVNG G is said to be a maximum SM.Theorem 10.
LetG=V,E be an SVNG; then(34)D11G=maxM1O˜¨|O˜¨is an SM inGwithO˜¨≤n2,D21G=maxM2O˜¨|O˜¨is an SM inGwithO˜¨≤n2,D31G=minM3O˜¨|O˜¨is an SM inGwithO˜¨≤n2,where n denotes the number of vertices in G=V,E.Proof.
As each vertex of a complete SVNGG is connected to every other vertex in G and all of its edges are strong, the SM number of G is n/2, since each edge is strong in a complete SVNG and crisp graph; therefore the SM numbers in both graphs are the same [49]. So, in the SM of G, n/2 is the greatest number of edges. Thus,(35)D11G=maxM1O˜¨|O˜¨is an SM inGwithO˜¨≤n2,D21G=maxM2O˜¨|O˜¨is an SM inGwithO˜¨≤n2,D31G=minM3O˜¨|O˜¨is an SM inGwithO˜¨≤n2.Theorem 11.
IfK is a complete bipartite SVNG with V1 and V2 as partite sets, then(36)D11G=maxM1O˜¨|O˜¨is an SM inKwithO˜¨≤minV1,V2,D21G=maxM2O˜¨|O˜¨is an SM inKwithO˜¨≤minV1,V2,D31G=minM3O˜¨|O˜¨is an SM inKwithO˜¨≤minV1,V2.Proof.
SinceK is a complete bipartite SVNG, all of its edges are strong. Moreover, each of the vertices in V1 is connected to all the vertices in V2 and each of the vertices in V2 is connected to all the vertices in V1. The matching number of K is V1,V2, since each edge is strong in a complete bipartite SVNG and complete bipartite crisp graph; therefore, the SM numbers in both graphs are the same [49]. So, in the SM of K, V1,V2 is the greatest number of edges. Thus,(37)D11G=maxM1O˜¨|O˜¨is an SM inKwithO˜¨≤minV1,V2,D21G=maxM2O˜¨|O˜¨is an SM inKwithO˜¨≤minV1,V2,D31G=minM3O˜¨|O˜¨is an SM inKwithO˜¨≤minV1,V2.Theorem 12.
IfG=V,E is SVNC and g¯ is a CC, then(38)DG=maxM1O˜¨|O˜¨is an SM inGwithO˜¨≤n2,D21G=maxM2O˜¨|O˜¨is an SM inGwithO˜¨≤n2,D31G=minM3O˜¨|O˜¨is an SM inGwithO˜¨≤n2.Proof.
Every edge of an SVNCG is strong. Moreover, n/2 is the SM number of G, and since each edge is strong in both of G and g¯, both graphs possess the same number of edges in SM [49]. So, in the SM of G, n/2 is the greatest number of edges. Thus,(39)D11G=maxM1O˜¨|O˜¨is an SM inGwithO˜¨≤n2,D21G=maxM2O˜¨|O˜¨is an SM inGwithO˜¨≤n2,D31G=minM3O˜¨|O˜¨is an SM inGwithO˜¨≤n2.Example 4.
Figure4 displays an SVNG G=V,E. In G, the edges represented by solid lines a,β,a,c, and c,d are the SEs, while β,d is not an SE, which is represented by dotted line. So, the SVCs are S˙˙1=a,c, S˙˙2=a,d, S˙˙3=β,c, S˙˙4=a,β,c, S˙˙5=a,c,d, S˙˙6=a,β,d, S˙˙7=β,c,d, and S˙˙8=a,β,c,d.
Now, by the definition of the value of SVC,(40)MS˙˙=M1S˙˙,M2S˙˙,M3S˙˙=∑u∈S˙˙m2u,v,∑u∈S˙˙α2u,v,∑u∈S˙˙n2u,v,the following results are obtained for each SVC: MS˙˙1=0.2+0.2,0.4+0.4,0.7+0.8=0.4,0.8,1.5; similarly,(41)MS˙˙2=0.5,0.9,1.5,MS˙˙3=0.8,1.1,1.0,MS˙˙4=1.0,1.5,1.7,MS˙˙5=0.7,1.3,2.3,MS˙˙6=1.1,1.6,1.7,MS˙˙7=1.1,1.6,1.8,MS˙˙8=1.3,2.0,2.5.
The SVC number ofG is C0=C10,C20,C30=0.4,0.8,2.5. In this case, there is no minimum strong independent cover. In this case, there is no minimum SVC.
The verticesa and d are strongly independent since they are not linked by an SE. But they are not independent because are they adjacent.
The SISs areS˙˙1=a,d, S˙˙2=β,d, and S˙˙3=β,c.
Now, the value of strong independent cover is calculated by using(42)MS˙˙=M1S˙˙,M2S˙˙,M3S˙˙=∑u∈S˙˙m2u,v,∑u∈S˙˙α2u,v,∑u∈S˙˙n2u,v.
Thus,MS˙˙1=0.2+0.3,0.4+0.5,0.7+0.8=0.5,0.9,1.5; similarly,(43)MS˙˙2=0.8,1.1,1.0,MS˙˙3=0.9,1.2,1.0.
The strong independent number ofG is D0=D10,D20,D30=0.9,1.2,1.0. The maximum SIS is S˙˙3 with MS˙˙3=D0.
The SECs areT˙1=a,β,c,d and T˙2=a,β,a,c,c,d.
The value of SEC is calculated by(44)MT˙=M1T˙,M2T˙,M3T˙=∑u,v∈T˙m2u,v,∑u,v∈T˙α2u,v,∑u,v∈T˙n2u,v.
Consequently,MT˙1=0.6+0.3,0.7+0.5,0.2+0.8=0.9,1.2,1.0 and MT˙2=1.1,1.6,1.7 are the values of SECs T˙1 and T˙2, respectively. So, the SEC number is C1=C11,C,C31=0.9,1.2,1.7. None of the strong covers is a minimum SEC.
The only SM ofG is O˜¨=a,β,c,d. The SM number is defined by(45)MO˜¨=M1O˜¨,M2O˜¨,M3O˜¨=∑u,v∈O˜¨mu,v,∑u,v∈O˜¨α2u,v,∑u,v∈O˜¨n2u,v.
Thus,MO˜¨=0.6+0.3,0.7+0.5,0.2+0.8=0.9,1.2,1.0 is the SM number.Figure 4
Strong covering in SVNG.Theorem 13.
LetG=V,E be an SVNG of order m,n which does not contain any isolated vertices; then, for every such graph,(i)
C0+D0=MV≤m(ii)
C1+D1≥nProof.
LetY˙0 be the minimum SVC of G and C0=MY˙0. Then V−Y˙0 is an SIS of vertices. That means V−Y˙0 contains such vertices that are incident on SEs of G. So, D0≥MV−Y˙0=MV−C0.(46)i.e.C0+D0≥MV.
LetZ^0 be the maximum SIS of vertices in G and D0=MZ^0. It means Z^0 does not contain any vertices that are connected to each other via SE and therefore all the SEs of G are strongly covered by the vertex in V−Z^0. Hence, V−Z^0 is an SVC of G with smallest value C0. Therefore, C0≤MV−Z^0=MV−D0.(47)i.e.C+D0≤MV.
Using (46) and (47),(48)C0+D0=MV.
By definition,MV is as follows:(49)MV≤m.
Hence,(50)C0+D0=MV≤m.
AsC1andD1 are determined by considering the value of the SEs and the sum of the vertex values is represented by m, the second inequality follows directly.Definition 14.
Suppose thatO˜¨ is an SM in an SVNG G=V,E and if O˜¨ strongly matches all vertices of G to some vertices of G, then O˜¨ is said to be perfect strong matching (PSM).Example 5.
All of the edges of an SVNGG=V,E are strong and are represented by solid lines, as shown in Figure 5. Therefore, the SMs are the collection of O˜¨1=a,β,c,d, O˜¨2=a,c,β,d, and O˜¨3=a,d,β,c. Moreover, each of the collections O˜¨1,O˜¨2, and O˜¨3 is also a PSM. The SM number is calculated by(51)MO˜¨=M1O˜¨,M2O˜¨,M3O˜¨=∑u,v∈O˜¨m2u,v,∑u,v∈O˜¨α2u,v,∑u,v∈O˜¨n2u,v.
Hence, the SM numbers are(52)MO˜¨1=0.4+0.3,0.3+0.2,0.8+0.6=0.7,0.5,1.4.
Similarly,MO˜¨2=0.4,0.7,1.5 and MO˜¨3=0.4,0.5,1.5.Figure 5
Perfect strong matching in SVNG.


## 4. Paired Domination in Single-Valued Neutrosophic Graph

This section introduces the concept of paired domination (PD), strong paired domination (SPD), and perfect paired domination. A couple of theorems are proved, and examples are also given to explain the concepts.Definition 15.
Suppose thatG denotes an SVNG and v is a vertex in G; then, each of the neighbors of v and v itself is strongly dominated by v, which means that the vertices in Y˙v are strongly dominated by v. If every vertex of VG−S˙˙ is a strong neighbor of some vertex in S˙˙ of vertices of G, then S˙˙ is a strong dominating collection of G.Definition 16.
M1S˙˙=∑u∈S˙˙m2u,v is the membership value, M2S˙˙=∑u∈S˙˙α2u,v is the abstinence value, and M3S˙˙=∑u∈S˙˙n2u,v is the nonmembership value of the strong dominating collection S˙˙, where m2u,v and α2u,v represent the minimum of membership values and minimum of abstinence values of the SEs incident on u, while n2u,v represents the maximum of the values of nonmembership of such edges.
BG=B=B1,B2,B3 denotes and defines the strong domination number of an SVNG G, where B1 and B2 represent the minimum membership value and minimum abstinence value of strong dominating collections of G, while B3 represents the maximum nonmembership value of such collections.Definition 17.
If a collectionS˙˙⊆V of vertices of an SVNG G=V,E such that S˙˙ is a strong dominating collection and the induced single-valued neutrosophic subgraph (SVNSG) S˙˙ has a perfect strong matching, then S˙˙ is called a strong paired dominating collection. M1S˙˙=∑u∈S˙˙m2u,v and M2S˙˙=∑u∈S˙˙α2u,v are the membership value and abstinence value of the strong paired dominating collection S˙˙, while M3S˙˙=∑u∈S˙˙n2u,v is the nonmembership value of S˙˙, where m2u,v and α2u,v represent the minimum values of the membership and minimum values of the abstinence of SEs incident on u, while n2u,v represents the maximum values of the nonmembership of such edges.
δG=δ=δ1,δ2,δ3 denotes and defines the SPD number of an SVNG G, where δ1 and δ2 represent the minimum membership value and minimum abstinence value of strong paired dominating collections of G, while δ3 represents the greatest nonmembership value of such sets.Example 6.
Figure6 displays an SVNG G=V,E. In G, the edges represented by solid lines a,β,a,c, and c,d are the SEs, while β,d is not a SE, which is represented by a dotted line. So, the strong dominating collections are S˙˙1=a,β, S˙˙2=c,d, and S˙˙3=a,β,c,d.
Now, the values of strong dominating collections are to be found by(53)MS˙˙=M1S˙˙,M2S˙˙,M3S˙˙=∑u∈S˙˙m2u,v,∑u∈S˙˙α2u,v,∑u∈S˙˙n2u,v.
Therefore,MS˙˙1=0.2+0.6,0.4+0.7,0.7+0.2=0.8,1.1,0.9.
Similarly,MS˙˙2=0.5,0.9,1.6 and MS˙˙3=1.3,2.0,2.5.
The SPD number is defined as(54)δG=δ1,δ2,δ3.
Thus,δG=0.5,0.9,2.5 is the SPD number of SVNG in Figure 6.Figure 6
Paired domination in SVNG.Theorem 14.
IfG=V,E is a complete SVNG, then δ1G=2m2u,v, δ2G=2α2u,v, and δ3G=2n2u,v, where m2u,v, α2u,v, and n2u,v are the membership, abstinence, and nonmembership values of the weakest edge in G.Proof.
Since, by definition of a complete SVNGG, each vertex of G is connected to every other vertex in G and all of its edges are strong, let u,v be two vertices in any collection of G, then a strong paired dominating collection is formed by such set. Thus, δ1G=m2u,v+m2u,v=2m2u,v, δ2G=α2u,v+α2u,v=2α2u,v, and δ3G=n2u,v+n2u,v=2n2u,v.Theorem 15.
The SPD numbers for a complete bipartite SVNGK are δ1K=2m2u,v, δ2K=2α2u,v, and δ3K=2n2u,v, where m2u,v, α2u,v, and n2u,v are the membership, abstinence, and nonmembership values of the weakest edge in K.Proof.
By definition ofK, all of its edges are strong. Moreover, each of the vertices in V1 is connected to all the vertices in V2. Therefore, any collection in K which contains two vertices, one in V1 and the other in V2, is a strong paired dominating collection. Let u,v be the end vertices of any weakest edge u,v in K such that u∈V1 and v∈V2; then u,v makes a strong paired dominating collection.
Thus,δ1K=m2u,v+m2u,v=2m2u,v, δ2K=α2u,v+α2u,v=2α2u,v, and δ3K=n2u,v+n2u,v=2n2u,v.


## 5. Conclusion

Single-valued neutrosophic sets are characterized by three independent fuzzy-valued mappings, that is, membership grade, abstinence grade, and nonmembership grade. This research presented the notions of covering, matching, and paired domination using the strong edges in the neutrosophic environment. Furthermore, this paper discussed the concepts of strong vertices, strong edges, strong vertex cover, strong edge cover, strong vertex covering number, strong edge covering number, strong independent number, strong matching, and strong paired domination number in SVNG by strong edges with suitable examples. Moreover, the strong independent number, the strong matching, and the strong paired domination number of complete SVNG and complete bipartite are determined. The relations among these notions and numerous interesting properties are also proposed. Many interesting results of covering, matching, and paired domination are obtained and proved for SVNGs, complete SVNGs, SVNC, and complete bipartite SVNGs.



---

*Source: 5518295-2021-04-19.xml*