Nordhaus–Gaddum type results for graph irregularities

摘要

A graph whose vertices have the same degree is called regular. Otherwise, the graph is irregular. In fact, various measures of irregularity have been proposed and examined. For a given graph G=(V,E) with V={v1,v2,…,vn} and edge set E(G), di is the vertex degree where 1 ≤ i ≤ n. The irregularity of G is defined by irr(G)=∑vivj∈E(G)|di−dj|. A similar measure can be defined by irr2(G)=∑vivj∈E(G)(di−dj)2. The total irregularity of G is defined by irrt(G)=12∑vi,vj∈V(G)|di−dj|. The variance of the vertex degrees is defined var(G)=1n∑i=1ndi2−(2mn)2. In this paper, we present some Nordhaus–Gaddum type results for these measures and draw conclusions.