Nordhaus–Gaddum type results for graph irregularities

Yuede Ma, Shujuan Cao, Yongtang Shi, Matthias Dehmer, Chengyi Xia

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)268-272
Number of pages5
JournalApplied Mathematics and Computation
Volume343
DOIs
Publication statusPublished - 15 Feb 2019

Keywords

  • Degree
  • Graph irregularity
  • Nordhaus–Gaddum
  • Regular graph
  • Zagreb index

Fingerprint Dive into the research topics of 'Nordhaus–Gaddum type results for graph irregularities'. Together they form a unique fingerprint.

Cite this