TY - JOUR
T1 - Nordhaus–Gaddum type results for graph irregularities
AU - Ma, Yuede
AU - Cao, Shujuan
AU - Shi, Yongtang
AU - Dehmer, Matthias
AU - Xia, Chengyi
N1 - Publisher Copyright:
© 2018 Elsevier Inc.
Copyright:
Copyright 2018 Elsevier B.V., All rights reserved.
PY - 2019/2/15
Y1 - 2019/2/15
N2 - 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={v 1 ,v 2 ,…,v n } and edge set E(G), d i is the vertex degree where 1 ≤ i ≤ n. The irregularity of G is defined by irr(G)=∑ v i v j ∈E(G) |d i −d j |. A similar measure can be defined by irr 2 (G)=∑ v i v j ∈E(G) (d i −d j ) 2 . The total irregularity of G is defined by irr t (G)=[Formula presented]∑ v i ,v j ∈V(G) |d i −d j |. The variance of the vertex degrees is defined var(G)=[Formula presented]∑ i=1 n d i 2 −([Formula presented]) 2 . In this paper, we present some Nordhaus–Gaddum type results for these measures and draw conclusions.
AB - 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={v 1 ,v 2 ,…,v n } and edge set E(G), d i is the vertex degree where 1 ≤ i ≤ n. The irregularity of G is defined by irr(G)=∑ v i v j ∈E(G) |d i −d j |. A similar measure can be defined by irr 2 (G)=∑ v i v j ∈E(G) (d i −d j ) 2 . The total irregularity of G is defined by irr t (G)=[Formula presented]∑ v i ,v j ∈V(G) |d i −d j |. The variance of the vertex degrees is defined var(G)=[Formula presented]∑ i=1 n d i 2 −([Formula presented]) 2 . In this paper, we present some Nordhaus–Gaddum type results for these measures and draw conclusions.
KW - Degree
KW - Graph irregularity
KW - Nordhaus–Gaddum
KW - Regular graph
KW - Zagreb index
UR - http://www.scopus.com/inward/record.url?scp=85054808841&partnerID=8YFLogxK
U2 - 10.1016/j.amc.2018.09.057
DO - 10.1016/j.amc.2018.09.057
M3 - Article
SN - 1873-5649
VL - 343
SP - 268
EP - 272
JO - Applied Mathematics and Computation
JF - Applied Mathematics and Computation
ER -