Operations on Fuzzy Incidence Graphs and Strong Incidence Domination Kavya. R. Nairand M. S. Sunitha

2025-05-02 0 0 707.09KB 15 页 10玖币

侵权投诉

Operations on Fuzzy Incidence Graphs and Strong

Incidence Domination

Kavya. R. Nair ∗and M. S. Sunitha †

Department of Mathematics, National Institute of Technology, Calicut, Kerala, India-673601

Abstract

Fuzzy incidence graphs (FIG) model real world problems eﬃciently when there is an extra attribute of

vertex- edge relationship. The article discusses the operations on Fuzzy incidence graphs. The join, Cartesian

product, tensor product, and composition of FIGs are explored. The study is concentrated mainly on strong

fuzzy incidence graphs (SFIG). The idea of strong incidence domination (SID) is used, and strong incidence

domination number (SIDN) in operations is examined. Basic properties of FIGs obtained from the operations

are studied. Bounds for the domination number of product of two SFIGs are determined for the Cartesian and

tensor products. Study is conducted on FIGs with strong join and composition. Complete fuzzy incidence

graphs (CFIGs) and FIGs with eﬀective pairs are also considered in the study.

Keywords: Fuzzy incidence graphs, Weak fuzzy incidence cycle, Cartesian product, join, tensor product,

composition, strong fuzzy incidence graphs.

1 Introduction

With the introduction of fuzzy set theory by Zadeh [1] in 1965, the theory has evolved in various ways across

numerous ﬁelds. The theory has wide range of applications in operation research, pattern recognition, decision

theory, artiﬁcial intelligence etc. Graph-theoretical principles are frequently employed in the research and mod-

eling of diverse applications in various ﬁelds. However, in many circumstances, graph-theoretical notions are

ambiguous and imprecise. In such cases it is suitable to use fuzzy set approaches to cope with ambiguity and

uncertainty. This led to the introduction of fuzzy graph (FG) theory by Rosenfeld [2] in 1975. The introduction

of fuzzy incidence graphs (FIG) was motivated by a FG model with the extra attribute of vertices having some

eﬀect on the edges. Dinesh [3] developed the term FIG in 2016 and studied some of its properties. The idea

of connectivity and fuzzy end nodes is developed by Mordeson et al. [4, 5]. It is often customary to study and

perform operations on graph structures to obtain new structures from the existing ones. Since the 1950s, a

number of graph products have been investigated. The operations on fuzzy graphs are discussed by Mordeson

and Peng [6]. Parvathi et al. [7] examined several intuitionistic fuzzy graph (IFG) operations such as Cartesian

product and composition. Sahoo and Pal [8] explored direct product, strong product and semistrong product

in IFGs. Nazeer et al. studied the intuitionistic fuzzy incidence graphs (IFIG) products in [9]. The research

on domination theory in graphs and fuzzy graphs expanded over the years due to its applications in numerous

ﬁelds. The concept of domination emerged in the 1850s with the chessboard domination problem. Ore [10] and

Berge [11] pioneered the study of domination in graphs in 1962. Signiﬁcant works on fuzzy graph domination and

domination in fuzzy graph products have been done in [12–17]. Nazeer et al. [18, 19] proposed FIG domination

based on eﬀective pairs and deﬁned strong domination in FIG and their join. Afsharmanesh et al. [20] recently

proposed domination using valid edges in FIGs. Kavya and Sunitha [21] deﬁned strong incidence domination

using weight of strong pairs.

The study is motivated by the fact that the pairs in every FIG may be characterised as strong or non-strong.

Hence the idea of SID developed can always be applied in any FIG. Furthermore, unlike other domination pa-

rameters that use the weight of vertices, SID uses the weight of strong pairs. As a result, the SID yields the

lowest value. Also, graph operations are always beneﬁcial for generating new structures from the already known

structures. Hence the study on operations on FIG is conducted, and the idea of SID is applied to the obtained

graphs.

The article studies some of the operations on FIGs. The study mainly deals with the join, Cartesian product,

tensor product, and composition of SFIGs. Section 1 sums up the preliminaries. Section 2 discusses the join

of FIGs and SID in the join. A characterisation for a FIG to be a SFIG is proved. It is illustrated with an

example that the join of two SFIG need not be strong in general. A suﬃcient condition for the join to be strong

∗Corresponding author. Kavya. R. Nair, Department of Mathematics, National Institute of Technology, Calicut, Kerala, India.

Email: kavyarnair@gmail.com

†sunitha@nitc.ac.in

arXiv:2210.14092v1 [math.CO] 25 Oct 2022

is considered. Section 3 and 4 deal with the Cartesian and tensor products of SFIGs and FIGs with eﬀective

pairs respectively. Section 4 studies the composition of SFIGs. A suﬃcient condition for the composition to be

strong is proved. Bound for the SIDN is obtained in each of the sections.

2 Preliminaries

The following deﬁnitions are taken from [3–5, 9, 18, 19, 21]. Throughout the article minimum and maximum

operators are represented by ∧and ∨respectively. A triple X= (V, E, I) such that Vis non-empty, E⊆

V×Vand I⊆V×Eis an incidence graph (IG).

Elements in I are called incidence pairs or pairs and are of the form (x, yz) where x∈Vand e0=yz ∈E.

If (w, xw),(x, xw),(y, yz) and (z, yz) are in I, then the edges wx and yz are considered adjacent.

An incidence subgraph, Yof Xis an IG having all its vertices, edges and pairs in X.

A sequence of vertices, edges and pairs starting at x0and ending at y0, where x0, y0∈V∪Eis called an incidence

walk from x0to y0. An incidence trail is an incidence walk with distinct pairs. If the vertices in an incidence

walk are distinct , then it is called an incidence path. If each vertex in an IG is joined to every other vertex by a

path, then the IG is connected. A component of an IG is a maximally connected incidence subgraph of the IG.

Let X= (V, E) be a graph. Let εand ρbe fuzzy subsets of Vand E⊆V×Vrespectively. Then X= (V, ε, ρ)

is fuzzy graph(FG) of Xif ρ(xy)≤ε(x)∧ε(y) for all x, y ∈V. Also, if η(v0, e0)≤ε(v0)∧ρ(e0), for all

v0∈Vand e0∈E, then ηis the fuzzy incidence of X. And, ˜

X= (ε, ρ, η) is called fuzzy incidence graph (FIG)

of X.

Here, ε∗, ρ∗and η∗are deﬁned as ε∗={x∈V:ε(x)>0},ρ∗={e0∈E:ρ(e0)>0}, and η∗={(x, xy)∈I:

η(x, xy)>0}. If |ε∗|= 1, then the FIG is called trivial.

Also, X= (V, ε, ρ) and X∗= (V, ε∗, ρ∗) are the underlying FG of ˜

Xand underlying graph of Xrespectively.

Let xy ∈ρ∗, if (x, xy),(y, xy)∈η∗, then xy is an edge in ˜

X. Pairs in FIG, ˜

Xare elements of the form (x, xy).

If vertices xand yare joined by a path, then xand yare connected in ˜

X. If each vertex is joined to every

other vertex by a path, then ˜

Xis connected. A fuzzy incidence subgraph ˜

Y= (ϕ, ξ, ζ) of ˜

Xis such that

ϕ⊆ε, ξ ⊆ρ, and ζ⊆ηand ˜

Yis a fuzzy incidence spanning subgraph of ˜

Xif ϕ=ε. If ϕ=ε, ξ =ρ, and ζ=η

for elements in ϕ∗, ξ∗, ζ∗respectively, then ˜

Yis a subgraph of ˜

A FIG, ˜

Xis complete fuzzy incidence graph (CFIG) if η(x, xy) = ∧{ε(x), ρ(xy)}for all (x, xy)∈V×Eand

ρ(xy) = ε(x)∧ε(y) for all (x, y)∈V×V. A pair (x, xy) is an eﬀective pair if η(x, xy) = ∧{ε(x), ρ(xy)}.

In a FIG ˜

X, a path from s0to t0where s0, t0∈ε∗∪ρ∗, is called an incidence path. The minimum of the η

values of pairs in an incidence path is the incidence strength of that path. Here, η∞(x, yz) or ICONN ˜

X(x, yz)

is denoted as the incidence strength of path from xto yz of greatest incidence strength.

If ˜

X∗= (ε∗, ρ∗, η∗) is a cycle, then ˜

Xis a cycle. In addition, ˜

Xis a fuzzy cycle (FC), if there exists no unique

edge xy ∈ρ∗with the least weight. A FIG, ˜

X= (ε, ρ, η) is a fuzzy incidence cycle (FIC) if ˜

Xis a FC and there

is no unique (x, xy)∈η∗with the least weight.

Let ˜

X= (ε, ρ, η) be a FIG, η0∞(x, yz) is the greatest incidence strength among the incidence strength of all

paths from xto yz in ˜

G\(x, yz). If η(x, xy)> η0∞(x, xy), then the pair (x, xy) is α−strong. Pair (x, xy) is

β−strong if η(x, xy) = η0∞(x, xy), and is a δ−pair if η(x, xy)< η0∞(x, xy). A strong pair is α−strong or β−

strong pair. Vertex xand edge xy are strong fuzzy incidence neighbors if (x, xy) is strong. A path with strong

pairs is called strong incidence path (SIP). A FIG with only strong pairs is called a strong fuzzy incidence graph

(SFIG).

If both (x, xy) and (y, xy) are strong, then xis called strong incidence neighbor (SIN) of y. Also, NI S (x) is the

strong incidence neighborhood of x, which is the set of all SINs of x. If x=yor xis a SIN of y, then xdominates

y. Isolated vertex xis such that NIS (x) = φ. A set ˜

D⊆Vin ˜

Xis a strong incidence dominating set (SIDS), if

for any x∈V−˜

D,∃some y∈˜

Dsuch that, xis a SIN of y.

Here, W(˜

D) is the weight of SIDS, ˜

D, deﬁned as

W(˜

D) = X

x∈˜

η(x, xy)

where η(x, xy) is minimum weight of strong pairs at xand y∈NIS (x). The strong incidence domination number

(SIDN), denoted as γIS (˜

X) or γIS is the minimum weight of the SIDSs in the FIG, ˜

X. A minimum SIDS is a

SIDS with minimum weight.

3 Strong incidence domination in Join of Fuzzy Incidence Graph

This section studies the SID in join of FIGs. The section begins with the deﬁnition of a WFIC. Theorem 3.4

is a characterisation for a FIG to be strong. It is established that the join of two SFIG need not be strong.

Proposition 3.8 proves a necessary condition for the join of two FIGs to be strong. A suﬃcient condition for the

join of two FIGs to be strong is also proved in Theorem 3.10. Theorem 3.13 and its corollaries discuss the SIDN

and SIDS in the join of FIGs.

Remark 3.1. The deﬁnition of weak fuzzy incidence cycle (WFIC) is given in Deﬁnition 3.2. A WFIC is

diﬀerent from a FIC, since it is not necessary for the underlying FG of a WFIC to be a FC. An example of a

WFIC is illustrated in Example 3.3.

Deﬁnition 3.2. Let ˜

X= (ε, ρ, η)be a FIG such that (ε∗, ρ∗, η∗)is a cycle and there is no unique (a, ab)∈η∗

such that η(a, ab) = ∧{η(c, cd)|(c, cd)∈η∗}. Then ˜

Xis called a weak fuzzy incidence cycle (WFIC).

y(1) v(1)

w(1)x(1)

u(1)

0.3

0.2

0.3

0.5

0.1

0.3

0.2

0.3

0.5

0.1

Fig. 1. Weak fuzzy incidence cycle ˜

Example 3.3. The FIG, ˜

Xin Fig. 1. is an example of WFIC, but ˜

Xis not a FIC, since the underlying FG

is not a FC.

Theorem 3.4. A FIG, ˜

Xis a SFIG iﬀ every cycle in ˜

Xis a WFIC.

Proof. Let ˜

Xbe a FIG such that every cycle in ˜

Xis a WFIC. Let (a, ab) be a pair in ˜

X. Then there are 3

cases:

Case 1: (a, ab) does not belongs to any cycle of ˜

Then (a, ab) is a strong pair.

Case 2: In every cycle that contains (a, ab), (a, ab) is a pair with least weight.

Since every cycle in ˜

Xis a WFIC this implies that η(a, ab) = ICONN ˜

X\(a,ab)(a, ab), i.e, (a, ab) is a strong pair.

Case 3: There exists at least one cycle ˜

Ccontaining (a, ab), in which (a, ab) is not a pair with least weight.

Then η(a, ab) is greater than the incidence strength of the path ˜

C\(a, ab), which implies that η(a, ab)≥

ICON N ˜

X\(a,ab)(a, ab) i.e, (a, ab) is a strong pair.

Since (a, ab) is arbitrary, it implies that ˜

Xis a SFIG.

Conversely, suppose that ˜

Xis a SFIG. Suppose that ˜

Cis a cycle that is not WFIC. Then there exists a pair

(a, ab) in ˜

Csuch that (a, ab) is the unique weakest pair in ˜

C. The path ˜

C\(a, ab) has incidence strength greater

than η(a, ab). Hence η(a, ab)< ICONN ˜

X\(a,ab)(a, ab), i.e, (a, ab) is a δ−pair, which contradicts the assumption.

Hence the result.

The deﬁnition of join of FIGs is taken from [19].

Deﬁnition 3.5. [19] Let ˜

X1= (ε1, ρ1, η1)and ˜

X2= (ε2, ρ2, η2)be two FIGs. Then the join of ˜

X1and ˜

denoted as ˜

X1⊕˜

X2is the FIG, ˜

X= (ε, ρ, η)such that:

ε(a) = (ε1(a)if a ∈˜

ε2(a)if a ∈˜

ρ(ab) = 









ρ1(ab)if a, b ∈˜

ρ2(ab)if a, b ∈˜

ε1(a)∧ε2(b)if a ∈˜

X1and b∈˜

η(a, ab) =











η1(a, ab)if (a, ab)∈˜

η2(a, ab)if (a, ab)∈˜

ε1(a)∧ε2(b)∧η1(a, avi)if a ∈˜

X1and b∈˜

where vi∈˜

ε1(b)∧ε2(a)∧η2(a, avi)if b ∈˜

X1and a∈˜

where vi∈˜

Remark 3.6. In general, the join of two SFIGs need not be strong. Example 3.7 illustrates that join of two

SFIGs need not be SFIG.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

OperationsonFuzzyIncidenceGraphsandStrongIncidenceDominationKavya.R.Nair*andM.S.SunithaDepartmentofMathematics,NationalInstituteofTechnology,Calicut,Kerala,India-673601AbstractFuzzyincidencegraphs(FIG)modelrealworldproblemsecientlywhenthereisanextraattributeofvertex-edgerelationship.Thearticledisc...

展开>> 收起<<

Operations on Fuzzy Incidence Graphs and Strong Incidence Domination Kavya. R. Nairand M. S. Sunitha.pdf

共15页,预览3页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Operations on Fuzzy Incidence Graphs and Strong Incidence Domination Kavya. R. Nairand M. S. Sunitha

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: