# Weighted Graph Irregularity Indices Defined on the Vertex Set of a Graph

Authors: Zainab Alsheekhhussain; Tamás Réti; Akbar Ali
Journal: Journal of Mathematics
 (2022)

---

## Abstract

Performing comparative tests, some possibilities of constructing novel degree- and distance-based graph irregularity indices are investigated. Evaluating the discrimination ability of different irregularity indices, it is demonstrated (using examples) that in certain cases two newly constructed irregularity indices, namelyIRDEA and IRDEB, are more selective.


---

## Body

## 1. Introduction

Only connected graphs without loops and parallel edges are considered in this study. For a graphG with n vertices and m edges, VG and EG denote the sets of vertices and edges, respectively. Let du be the degree of vertex u of G. Let uv be an edge of G connecting the vertices u and v. Let Δ=ΔG and δ=δG be the maximum and the minimum degrees, respectively, of G. In what follows, we use the standard terminology in graph theory; for notations not defined here, we refer the readers to the books [1, 2].For a connected graphG, the set of numbers nj of vertices with degree j is denoted by nj=njG:nj>0,1≤j≤Δ. For simplicity, the numbers njG are called the vertex-parameters of graph G. For two vertices u,v∈VG, the distance du,v between u and v is the number of edges in a shortest path connecting them.Two connected graphsG1 and G2 are said to be vertex-degree equivalent if they have an identical vertex-degree sequence. Certainly, if G1 and G2 are vertex-degree equivalent, then their vertex-parameters sets satisfy the equation njG1=njG2 for every j. A graph is called k-regular if all its vertices have the same degree k. A graph which is not regular is called a nonregular graph. A connected graph G is said to be bidegreed if its degree set consists of only two elements, where a degree set of G is the set of all distinct elements of its degree sequence.


## 2. Preliminary Considerations

A topological indexTI of a graph G is any number associated with G (in some way) provided that the equation TIG=TIG′ holds for every graph G′ isomorphic to G. A lot of existing topological indices are degree- and distance-based ones [3–5]. Graph irregularity indices form a notable subclass of the class of traditional topological indices; where a topological index TI of a (connected) graph G is called a graph irregularity index if TIG≥0, and TIG=0 if and only if graph G is a regular graph. Details about the existing graph irregularity indices can be found in [6, 7]. The readers interested in the general concept of irregularity in graphs may consult the book [8].In several situations, it is crucial to know how much irregular a given graph is; for example, see [9, 10] where irregularity measures are used to predict physicochemical properties of chemical compounds, and see [11–14] for some applications of irregularity measures in network theory.Most of the existing irregularity indices used in mathematical chemistry are degree-based irregularity indices. There exist irregularity indices which form a particular subsetΦ of the set of degree-based irregularity indices; we say that an irregularity index ϕ belongs to the set Φ if for every pair of vertex-degree equivalent graphs G1 and G2, the equation ϕG1=ϕG2 holds.The most popular topological indices that are used in defining degree-based irregularity indices, are the first and second Zagreb indices (see for example [15]), denoted by M1 and M2, respectively, and the so-called forgotten topological index [15], denoted by F. The first and second Zagreb indices of a graph G are defined as(1)M1G=∑u∈VGdu2,M2G=∑uv∈EGdudv,and the forgotten topological index is defined as(2)FG=∑u∈VGdu3.There exist numerous degree-based graph irregularity indices in literature, some of them are listed below.The varianceVar is a degree-based graph irregularity index introduced by Bell [16]. The variance Var of a graph G of order n and size m is defined as(3)VarG=1n∑u∈VGdu−2mn2=M1Gn−4m2n2.We also consider the following four irregularity indices:(4)IRVG=n2VarG=nM1G−4m2,(5)IR1G=M1Gn−2mn,(6)IR2G=M2Gm−2mn,(7)IR3G=FG−2mnM1G.It is remarked here that, exceptIR2, all the irregularity indices formulated above belong to the set Φ.


## 3. Weighted Irregularity Indices Defined on the Vertex Set of a Graph

In this section, we consider irregularity indices defined on the set of vertices of a graphG. The majority of these indices are weighted degree- and distance-based topological indices. Most of them may be considered as extended versions of the Wiener index; for example, see [17]. Let us consider the weighted vertex-based topological index of a graph G formulated as(8)ZWG=12∑u,v∈VGZu,vWu,v,where Zu,v and Wu,v are appropriately selected non-negative 2-variable symmetric functions; both of them are defined on the vertex set VG of G. For simplicity, we call the function Wu,v as the weight function of G. By taking(9)Zu,v=du−dvp.in Equation (8), we get the following graph irregularity index(10)IRRpG=12∑u,v∈VGdu−dvpWu,v,where p is a positive real number. Depending on the choice of the parameter p and the weight function Wu,v, various types of irregularity indices can be deduced. For instance, the choices p=1 and Wu,v=1 lead to the so-called total irregularity of a graph G defined by(11)Irrt1G=12∑u,v∈VGdu−dv.It was introduced by Abdo et al. in [18]. Also, assuming that p=2 and Wu,v=1, we have the irregularity index Irrt2G, introduced in Ref. [19]:(12)Irrt2G=12∑u,v∈VGdu−dv2.At this point, the following known proposition [19] concerning Irrt2 needs to be stated.Proposition 1.
For every graphG with n vertices and m edges, it holds that(13)Irrt2G=12∑u,v∈VGdu−dv2=nM1G−4m2=n2VarG=IRVG.In Equation (9), by taking Zu,v=du−dv2 and Wu,v=du,v, we obtain the following irregularity index:(14)IRDG=12∑u,v∈VGdu−dv2du,v.Note thatIRD is a weighted degree- and distance-based irregularity index. Although IRD is a new irregularity index which is not known in the literature, but we prove in the next proposition that this irregularity index can be written in the linear combination of the following two topological indices(15)DGG=∑u∈VGdu2DGu,and(16)GutG=12∑u,v∈VGdudvdu,v,where DGu is identical to the transmission Tru of the vertex u∈VG and GutG is the so-called Gutman index; for example, see [20].Proposition 2.
For a (connected) graphG, it holds that(17)IRDG=12∑u,v∈VGdu−dv2du,v=DGG−2GutG.Proof.
Note that(18)12∑u,v∈VGdu−dv2du,v=12∑u,v∈VGdu2+dv2du,v−2GutG.For the graph G, it holds [21] that(19)12∑u,v∈VGωu+ωvdu,v=∑u∈VGωuDGu,where ωu is any quantity associated with the vertex u of G. By taking ωu=du2 in (19) and using the obtained identity in (18), we get(20)12∑u,v∈VGdu−dv2du,v=∑u∈VGdu2DGu−2GutG=DGG−2GutG.Remark 1.
From Proposition2, it follows that the inequality(21)DGG≥2GutGholds for every (connected) graph G, with equality if and only if G is regular.Remark 2.
BecauseIRD is a weighted version of the irregularity index Irrt2, it is expected that its discrimination power is better than that of Irrt2.Remark 3.
Based on identity Equation (20), one can establish another irregularity index IRQ defined by(22)IRQG=DGG−2GutG2GutG=DGG2GutG−1.
AsGutG>1/2 for every (connected) graph of order at least 3, one has(23)IRQG=DGG2GutG−1<DGG−2GutG=IRDG.


## 4. Discriminating Ability of Novel Weighted Irregularity Indices

For comparing the discrimination ability of the irregularity indicesIRD and IRQ with the traditional degree-based irregularity indices Var, IR1, IR2, and IR3, we use the 6-vertex graphs Gii=1,2,3,4 depicted in Figure 1. It is remarked here that the graphs shown in Figure 1 belong to the family of connected threshold graphs, and graph G1 is isomorphic to the connected 6-vertex antiregular graph (for example, see [22, 23]).Figure 1
Four 6-vertex nonregular graphs selected for tests.For the four graphs depicted in Figure1, computed values of preselected topological indices M1, M2, F, and corresponding irregularity indices are summarized in Tables 1 and 2.Table 1
Computed topological indices of the four graphs shown in Figure1.
GraphmM1M2FVarIR1IR2IR3G19641062525/30.2660.4319249.0G27445717017/90.3750.5202167.7G38547921417/90.3330.4758211.3G48548220817/90.3330.5349205.3Table 2
Computed topological indices of the four graphs shown in Figure1.
GraphmIrrt1Irrt2DGGutIRDIRQG192660388154800.2597G27266827095800.4211G382668326123800.3252G482668332120920.3833Comparing irregularity indices listed in Tables1 and 2, the following conclusions can be drawn. Among the four tested graphs, the index G1 achieves the maximum value (that is, 249) of IR3. The irregularity indices IR1 and IR2 are maximum for the graph G2 (namely, IR1G2≈0.375 and IR2G2≈0.5202). As it can be seen that VarG1≈1.667, while VarG2=VarG3=VarG3≈1.889 and that all the four graphs have the same value of Irrt1, which is 26. Also, the relation Irrt2G=n2VarG is confirmed for the considered graphs: Irrt2G1=60 and Irrt2G2=Irrt2G3=Irrt2G4=68. Moreover, we have IRDG1=IRDG2=IRDG3=80 and IRDG4=92, while the computed values of the irregularity index IRQ are different for all four graphs. From these observations, one can conclude that the degree variance Var, the total irregularity index Irr1, together with the irregularity indices Irr2, and IRD have a limited discrimination ability for the considered four graphs.


## 5. Novel Irregularity Indices Constructed by Using the External Weight Concept

The weight functionWu,v included in (9) can be considered as an “internal” weight function. Introducing the external weight concept, one can construct novel irregularity indices. By using them, the original sequence of previously determined irregularity values can be appropriately modified for a given set of graphs considered.By definition, an external weightEWG for a graph G is a positive-valued topological index computed as a function of one or more traditional topological indices. By means of an external weight EWG a novel irregularity index IREG can be created as defined below:(24)IREG=EWG×IRG,where IRG is an arbitrary irregularity index. By appropriately selected external weights EWG, one can establish several different versions of irregularity indices IREG satisfying some restrictions or desired expectations. As an example, consider the three external weights defined for a graph G of order n and size m as follows:(25)EWAG=m2100n,(26)EWBG=M2G+FGn2,(27)EWCG=12×GutG.Using the three external weights listed above, the following irregularity indices of new type are obtained:(28)IRDEAG=EWAG×IRDG,(29)IRDEBG=EWBG×IRDG,(30)IRDECG=EWCG×IRDG.For graphs shown in Figure 1, the computed external weights and the corresponding irregularity indices are summarized in Table 3.Table 3
Computed topological indices of the four graphs shown in Figure1.
GraphmEWAIRDEAEWBIRDEBEWCIRDECG190.135010.8009.944795.60.00320.2597G270.08176.5336.306504.40.00530.4211G380.10678.5338.139651.10.00410.3252G480.10679.8138.056741.10.00420.3833Comparing the computed irregularity indices mentioned in Table3, one can conclude that the graph G1 has the maximum irregularity indices IRDEAG1=10.8 and IRDEBG1=795.6, while the maximum value of the irregularity index IRDEC is attained by the graph G2 where IRDECG2=0.4211 (it should be emphasized here that the graph G1 is identical to the 6-vertex connected antiregular graph, and it is usually desired that the connected antiregular graph attains the maximum value of an irregularity index among all connected graphs of a fixed order.)It is remarked here that the irregularity indicesIRQ and IRDEC are identical to each other because(31)IRQG=DGG2GutG−1=DGG−2GutG2GutG=EWCG×IRDG=IRDECG.


## 6. Additional Considerations

An interesting open problem can be formulated as follows: find a deterministic relationship between the following weighted bond-additive indices (see [24]).(32)BApG=∑uv∈EGdu−dvpWu,vand weighted atoms-pair-additive indices(33)IRRpG=12∑u,v∈VGdu−dvpWu,v.Depending on the definitions of the above irregularity indices, we observe that there exist graphs for which the mentioned relationship is perfect. As an example, whenp=1 and Wu,v=du,v then for the wheel graph Wn of order n with n≥5, one has(34)12∑u,v∈VWndu−dvdu,v=∑uv∈EWndu−dv=ALWn,where AL is the Albertson irregularity index [25].The sigma indexσG of a graph G is defined (for example, see [26]) as(35)∑uv∈EGdu−dv2.This irregularity index is a natural generalization of the Albertson irregularity index. For the wheel graphWn of order n with n≥5, the following identity holds:(36)IRDWn=12∑u,v∈VWndu−dv2du,v=∑uv∈EWndu−dv2=σWn.It is possible to construct a particular graph family for which the concept outlined above can be extended. For two graphsJ1 and J2 with disjoint vertex sets, J1∪J2 denotes the disjoint union of J1 and J2. The join J1+J2 of J1 and J2 is the graph obtained from J1∪J2 by adding edges between every vertex of J1 and every vertex of J2.Proposition 3.
Define the bidegreed graphHn of order n as follows:(37)H=H0+∪j≥1Hj,where H0 is an r-regular graph and each Hj is an r′-regular graph. It holds that(38)BADpHn=12∑u,v∈VHndu−dvpdu,v=∑uv∈EHndu−dvp=ALpHn,where ALpG is a modified version of the generalized Albertson irregularity index (see [27]).Proof.
We note that(39)BADpHn=∑uv∈EHndu−dvp+∑uv∉EHndu−dvpdu,v.
Observe thatdx=dy for every pair of nonadjacent vertices x,y∈VHn, which implies that(40)∑uv∉EHndu−dvpdu,v=0.and hence Equation (39) yields the desired result.
As an example concerning Proposition3, consider the bidegreed graph H14 of order 14 and size 59 constructed as follows:(41)H14=C4+K3,3∪K4,where C4 is the (2-regular) cycle graph with 4 vertices, K3,3 is the (3-regular) complete bipartite graph of order 6, and K4 is the (3-regular) complete graph on 4 vertices (see Figure 2. The graph H14 contains ten vertices of degree 7 and four vertices of degree 12. Note that if uv∉EH14, then u∈VJ and v∈VK, where J,K∈K3,3,K4, and both the vertices u,v have the degree 7 in H14. Thus,(42)∑uv∉EH14du−dvpdu,v=0and the desired conclusion holds.Figure 2
The bidegreed graphH14.



---

*Source: 7834080-2022-06-28.xml*