# On Omega Index and Average Degree of Graphs

Authors: Sadik Delen; Musa Demirci; Ahmet Sinan Cevik; Ismail Naci Cangul
Journal: Journal of Mathematics
 (2021)

---

## Abstract

Average degree of a graph is defined to be a graph invariant equal to the arithmetic mean of all vertex degrees and has many applications, especially in determining the irregularity degrees of networks and social sciences. In this study, some properties of average degree have been studied. Effect of vertex deletion on this degree has been determined and a new proof of the handshaking lemma has been given. Using a recently defined graph index calledomega index, average degree of trees, unicyclic, bicyclic, and tricyclic graphs have been given, and these have been generalized to k-cyclic graphs. Also, the effect of edge deletion has been calculated. The average degree of some derived graphs and some graph operations have been determined.


---

## Body

## 1. Introduction

LetG=V,E be a finite, undirected, and simple graph, having V=n vertices and E=m edges. For a vertex v∈V, the number of edges of G meeting at v is denoted by dGv or dv and known as the degree of v. If the set of all vertex degrees of G is(1)D=1a1,2a2,3a3,…,ΔaΔ,where ais are nonnegative integers, then D is called the degree sequence of G. Here, Δ is the maximum vertex degree. For every graph G, there is a degree sequence. However, for a degree sequence, there may or may not exist a graph. If there is a graph, then D is said to be realizable. For every realizable degree sequence, there is at least one graph; usually, there are many.In [1], a new graph index called Ω index was defined by(2)ΩD=∑i=1Δi−2ai.Several properties ofΩ index were obtained in [1, 2].There are some graph invariants related to the vertex degrees. The density of a graphG measures how many edges are there in the set E of edges compared to the maximum possible number of edges between the vertices of G. For a simple graph, the maximum number of edges is attained when the graph is complete. In this case, this number would be nn−1/2. So, the density of G is(3)ρG=2mnn−1.Clearly, the density increases proportionally with the number of edges. Therefore, amongst all connected simple graphs havingn vertices, trees have the lowest density and complete graph Kn has the highest density which is 1.In this paper, we make use ofΩ index to study the properties of average degree dG¯ of a graph G which measures how many edges has G compared to the number of vertices, that is,(4)dG¯=2mn.From the definitions, we can easily deduce the following relation betweendG¯ and ρG:(5)n−1ρG=dG¯.Also, the following relations between theΩ index of a graph G and density and average degree can be deduced as follows:(6)ρG=ΩG+2nnn−1,dG¯=ΩGn+2.If all the vertices in a graph have the same degree, sayr, the graph is said r-regular. Most of the graphs are not regular and some graph indices have been defined to measure the irregularity of a graph. The Bell index of a graph G is defined by(7)BG=∑u∈VGdGu−2mn2,see [3], and the degree deviation index is defined by(8)SG=∑u∈VGdGu−2mn,In [4], the degree deviation is equal to the product of the order n of G with the discrepancy of the graph. Also, the Collatz–Sinogowitz index is defined by(9)CSG=λ1−2mn,where λ1 denotes the largest eigenvalue of the adjacency matrix [5]. Note that, in all these irregularity indices, the average degree of a graph is used. This makes the notion of the average degree of a graph important. In the recent paper [6], two new and structurally different irregularity indices IRA and IRB have been defined and compared with other existing irregularity measures. Naturally, this list can easily be extended to have new members of the family of irregularity indices.The structure of this paper is planned as follows. In Section2, two related notions, density and average degree, are studied and these two quantities are calculated for acyclic, unicyclic, bicyclic, tricyclic, and, in general, k-cyclic graphs. In Sections 3 and 4, the effects of vertex and edge deletion on average degree of a graph are formulized. In Sections 5 and 6, the average degree of some derived graphs and some binary graph operations are determined.


## 2. Density, Average Degree, and Cyclicness

A connected graphG having no faces is called acyclic. A graph having at least one face is named as cyclic; especially as unicyclic, bicyclic, tricyclic, etc., according to the number of faces which is 1,2,3, etc., respectively. Here, using the Ω index, graphs are classified according to their cyclicness, and for each case, the density of the graph is characterized as follows:(i)
IfG is acyclic, then ρG=2/n(ii)
IfG is unicyclic, then ρG=2/n−1(iii)
IfG is bicyclic, then ρG=2n+1/nn−1(iv)
IfG is tricyclic, then ρG=2n+2/nn−1(v)
IfG is k-cyclic, for k=0,1,2,…, then ρG=2n+k−1/nn−1Indeed, letG be a connected k-cyclic graph. By Theorem 1 in [1], we have k=ΩG/2+1, as G is connected. Hence, ΩG=2k−1, and by Corollary 3.4 in [1], we know that m=n+k−1.The following is a similar result for an average degree. The average vertex degree of a connectedk-cyclic graph is(10)dG¯=2n+k−1n.As a result, connected acyclic, unicyclic, bicyclic, tricyclic, etc., graphs have average degrees2n−1/n, 2, 2n+1/n, 2n+2/n, etc., respectively.


## 3. Effect of Vertex Deletion on Average Degree

Now, the effect of vertex deletion on average degree will be considered. Using the obtained formula successively, we give a result which helps to calculate the average degree of a large graph by means of the average degree of a much smaller graph. LetG−v be the graph obtained by deleting the vertex v together with dv edges incident to v. First, we have the following.Theorem 1.
The following recurrence relation holds:(11)n⋅dG¯−n−1d¯G−v1=2dGv1.Proof.
LetG be a connected simple graph of order n. Let v1∈VG have degree dGv1 in G. G−v1 is the graph obtained by deleting the vertex v1 together with dv1 edges incident to v1. Hence, deleting v1 from G reduces the degree of each of the dv1 neighbours of v1 by 1. So, the deletion of v1 from G reduces the total vertex degree of G by 2dv1. Hence,(12)d¯G−v1=∑u∈VGdu−2dv1n−1=n⋅dG¯−2dv1n−1,which gives the result.Applying Theorem1 recursively, we can give another proof of the handshaking lemma by labeling the vertices v1,v2,⋯,vn so that dv1≤dv2≤dvn.Corollary 1.
(handshaking lemma). In every graph, the sum of vertex degrees is equal to twice the number of edges, that is,(13)∑u∈VGdu=2m.Proof.
Applying Theorem1 successively to delete v1,v2,…,vn from G, respectively, we get the following equalities:(14)ndG¯−n−1d¯G−v1=2dv1n−1d¯G−v1−n−2d¯G−v1,v2=2dv2n−2d¯G−v1,v2−n−3d¯G−v1,v2,v3=2dv3⋮n−n−1d¯G−v1,v2,…,vn−1−n−nd¯G−v1,v2,…,vn=2dvn.j.
Adding all these side by side, we obtain the result.So, we deleted all the vertices one by one to prove handshaking lemma. What happens if we only delete some of the vertices? We answer this question in two steps.Theorem 2.
LetG be a connected simple graph of order n, size m, and average degree dG¯. If v1,v2,…,vk are pairwise nonadjacent vertices of G, then(15)d¯G−v1,v2,…,vk=2m−d1+d2+⋯+dkn−k,where di=dvi, for i=1,2,…,k.Proof.
Letm¯ and n¯ be the size and order of G−v1,v2,…,vk. Then, by definition, we have d¯G−v1,v2,…,vk=2m¯/n¯. Clearly, n¯=n−k as k vertices are deleted. When a vertex vi is deleted, note that di incident edges are also deleted. So, if we delete pairwise nonadjacent vertices v1,…,vk from G, a total of d1+d2+⋯+dk edges are also deleted giving that m¯=m−d1+d2+⋯+dk. It proves the result.Finally, if some pairs of the deleted vertices are adjacent, then we would have the following result.Theorem 3.
Ift pairs of the vertices v1,v2,…,vk are adjacent in G, then(16)d¯G−v1,v2,…,vk=2m−2d1+d2+⋯+dk+2tn−k.Proof.
The proof is quite similar to the one of Theorem2, except we need to deal with adjacent pairs of vertices. If vi and vj are two adjacent vertices in G, then the total number of neighbours of vi is di and the total number of neighbours of vj is dj. Hence, when deleting both vi and vj, we also delete di+dj−1 edges incident to at least one of vi or vj. Here, −1 comes as the edge between vi and vj which can only be deleted once, but it is incident to both vi and vj. So, when v1,…,vk are deleted from G, a total of 2d1+d2+⋯+dk−t edges are also deleted, giving the result.Example 1.
LetG be the graph in Figure 1, and let us delete v1,v2,v4,v5, and v6.
Note that the average degree ofG is 14/7=2. The graph G−v1,v2,v4,v5,v6 is in Figure 2 and has the average degree 2/2=1.
According to Theorem3,(17)1=2⋅7−22+2+2+2+1+67−5,as there are t=3 pairs of deleted vertices.Figure 1
A graphG.Figure 2
The graphG−v1,v2,v4,v5,v6.


## 4. Effect of Edge Deletion on Average Degree

We now determine the effect of edge deletion from a graph on the average vertex degree. LetG be a graph of order n and size m, and let e be an edge. The graph obtained by deleting the edge e from G is denoted by G−e. We have the following recurrence relation between the average degrees of G and G−e.Theorem 4.
The average degree ofG−e is related to the average degree of G by the following recurrence relation:(18)dG¯−d¯G−e=2n.Proof.
As deleting an edgee will reduce the number of edges by 1 and will not change the number of vertices, we know that(19)d¯G−e=∑u∈VGdGu−2n=n⋅dG¯−2n,giving the required result.


## 5. Average Degree of Some Derived Graphs

A derived graph is a graph obtained from a given graph after some operation. In that sense, many authors consider derived graphs as graph operations. Derived graphs help to determine a property of a given graph by calculating the same property of the derived graph. In this section, we determine the average degree of some derived graphs. The derived graphs under study are the line, total, jump, and semitotal line graphs.The line graphLG of a graph G is constructed as follows. For each edge in the graph G, we draw a new vertex of LG so that two edges in G, having a vertex in common, make an edge between their corresponding vertices in LG. It can be seen that the order and size of the line graph LG are nLG=mG=m and mLG=M1G/2−m, respectively, where M1G=∑u∈VGdGu2 is the famous topological graph index called the first Zagreb index. Indeed,(20)mLG=12∑e∈EGdGe=12∑e=uv∈EGdGu+dGv−2=12∑u∈VGdGu2−∑e∈EG1=M1G2−m.Hence, the average degree of the line graphLG is obtained as(21)d¯LG=M1G−2mGmG=M1Gm−2.The total graphTG of a graph G, also known as the generalization of the line graph, is the graph so that the vertex set of TG corresponds to the vertices and edges of G and two vertices are adjacent in TG iff their corresponding elements are either adjacent or incident in G. By the definition, one can deduce the order and size of the total graph TG as nTG=m+n and mTG=2m+M1G/2, respectively. Hence, we deduce the average degree of the total graph as(22)d¯TG=4m+M1Gm+n.Next, we study the average degree of the jump graph. The jump graphJG of a graph G is the complement of the line graph. That is, the jump graph JG of a graph G is the graph defined on the edge set EG of the graph G in which two vertices are adjacent if and only if they are not adjacent in G. The order and size of the jump graph are nJG=m and mJG=mm+1/2−1/2M1G, respectively. Hence, the average degree of JG is(23)d¯JG=m2+m−M1Gm=m+1−M1Gm.Finally, we consider the semitotal line graphT1G. Its vertex set is VG∪EG where two vertices are adjacent in T1G if and only if they are either adjacent or incident in G. Also, nT1G=m+n and mT1G=m+M1G/2, implying that(24)d¯T1G=2m+M1Gm+n.So, it is proved.Theorem 5.
LetG be a graph of order n and size m. Then, the average degree of the line graph LG, total graph TG, jump graph JG, and semitotal line graph T1G is as follows:(25)d¯LG=M1G−2mGmG=M1Gm−2,d¯TG=4m+M1Gm+n,d¯JG=m+1−M1Gm,d¯T1G=2m+M1Gm+n.


## 6. Average Degree of Some Graph Operations

LetG1=V1,E1 and G2=V2,E2 be two graphs such that EG1=m1 and EG2=m2. In this final section, we study the average degree of some graph operations, namely, union, join, and corona products of two graphs G1 and G2.The unionG1∪G2 of two graphs G1 and G2 having disjoint vertex and edge sets is obtained easily by taking union of vertex sets as its vertex set and the union of edge sets as the edge set.Theorem 6.
The average degree of the unionG1∪G2 of two graphs G1 and G2 is(26)d¯G1∪G2=2m1+m2n1+n2.Proof.
By the definition of union operation, we can write thatVG1∪G2=n1+n2 and EG1∨G2=m1+m2. This proves the result.For two graphsG1 and G2 with orders n1 and n2 and sizes m1 and m2, respectively, the join operation G1∨G2 of two graphs G1 and G2 having disjoint vertex sets VG1 and VG2 and edge sets EG1 and EG2 is the graph union G1∪G2 together with all the edges between VG1 and VG2.Theorem 7.
The average degree of the joinG1∨G2 of two graphs G1 and G2 is(27)d¯G1∨G2=2m1+m2+n1n2n1+n2.Proof.
By the definition, we can deduce thatVG1∨G2=n1+n2 and EG1∨G2=m1+m2+n1n2. Hence, the result follows.The corona productG1°G2 of two graphs G1 and G2 is defined to be the graph obtained by taking one copy of G1 (which has n1 vertices) and n1 copies of G2, and then, joining the ith vertex of G1 to every vertex in the ith copy of G2, for i=1,2,…,n1, we obtain the following.Theorem 8.
The average degree of the corona productG1°G2 of two graphs G1 and G2 is(28)d¯G1°G2=2m1+n1m2+n2n11+n2.Proof.
We know thatVG1°G2=n11+n2 and EG1°G2=m1+n1m2+n2limx⟶∞. This gives the required number.



---

*Source: 5565146-2021-11-12.xml*