Open AccessOn graph irregularity indices with particular regard to degree deviation
Author(s) -
Tamás Réti,
Igor Ž. Milovanović,
Emina I. Milovanović,
Marjan Matejić
Publication year - 2021
Publication title -
filomat
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.449
H-Index - 34
eISSN - 2406-0933
pISSN - 0354-5180
DOI - 10.2298/fil2111689r
Subject(s) - mathematics , combinatorics , graph , degree (music) , vertex (graph theory) , simple graph , discrete mathematics , regular graph , connectivity , line graph , graph power , physics , acoustics
Let G = (V,E), V = {v1, v2,..., vn}, be a simple connected graph of order n and size m, with vertex degree sequence d1 ? d2 ? ...? dn. A graph G is said to be regular if d1 = d2 =... = dn. Otherwise it is irregular. In many applications and problems it is important to know how irregular a given graph is. A quantity called degree deviation S(G) = ?ni=1 |di-2m/n| can be used as an irregularity measure. Some new lower bounds for S(G) are obtained. A simple formula for computing S(G) for connected bidegreed graphs is derived also. Besides, two novel irregularity measures are introduced.