Graph irregularity and its measures

被引:21
作者
Abdo, Hosam [1 ]
Dimitrov, Darko [2 ]
Gutman, Ivan [3 ]
机构
[1] Free Univ Berlin, Inst Informat, Berlin, Germany
[2] Fac Informat Studies, Novo Mesto, Slovenia
[3] Univ Kragujevac, Fac Sci, Kragujevac, Serbia
关键词
Irregularity (of graph); Irregularity measure; Degree (of vertex); VARIABLE NEIGHBORHOOD SEARCH; EXTREMAL GRAPHS; INDEXES; SIZE;
D O I
10.1016/j.amc.2019.04.013
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Let G be a simple graph. If all vertices of G have equal degrees, then G is said to be regular. Otherwise, G is irregular. There were various attempts to quantify the irregularity of a graph, of which the Collatz-Sinogowitz index, Bell index, Albertson index, and total irregularity are the best known. We now show that no two of these irregularity measures are mutually consistent, namely that for any two such measures, irr(X) and irr(Y) there exist pairs of graphs G(1), G(2), such that irr(X) (G(1)) > irr(X) (G(2)) but irr(Y)(G(1)) < irr(Y)(G(2)). This implies that the concept of graph irregularity is not free of ambiguities. (c) 2019 Published by Elsevier Inc.
引用
收藏
页码:317 / 324
页数:8
相关论文
共 40 条
[1]   THE TOTAL IRREGULARITY OF GRAPHS UNDER GRAPH OPERATIONS [J].
Abdo, H. ;
Dimitrov, D. .
MISKOLC MATHEMATICAL NOTES, 2014, 15 (01) :3-17
[2]  
Abdo H., 2015, INT J COMPUT APPL, V122, P1, DOI [10.5120/21846-5170, DOI 10.5120/21846-5170]
[3]   Graphs with maximal σ irregularity [J].
Abdo, Hosam ;
Dimitrov, Darko ;
Gutman, Ivan .
DISCRETE APPLIED MATHEMATICS, 2018, 250 :57-64
[4]   On the irregularity of some molecular structures [J].
Abdo, Hosam ;
Dimitrov, Darko ;
Gao, Wei .
CANADIAN JOURNAL OF CHEMISTRY, 2017, 95 (02) :174-183
[5]   NONREGULAR GRAPHS WITH MINIMAL TOTAL IRREGULARITY [J].
Abdo, Hosam ;
Dimitrov, Darko .
BULLETIN OF THE AUSTRALIAN MATHEMATICAL SOCIETY, 2015, 92 (01) :1-10
[6]   Graphs with Maximal Irregularity [J].
Abdo, Hosam ;
Cohen, Nathann ;
Dimitrov, Darko .
FILOMAT, 2014, 28 (07) :1315-1322
[7]   THE IRREGULARITY OF GRAPHS UNDER GRAPH OPERATIONS [J].
Abdo, Hosam ;
Dimitrov, Darko .
DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2014, 34 (02) :263-278
[8]  
Abdo H, 2014, DISCRETE MATH THEOR, V16, P201
[9]   HIGHLY IRREGULAR GRAPHS [J].
ALAVI, Y ;
CHARTRAND, G ;
CHUNG, FRK ;
ERDOS, P ;
GRAHAM, RL ;
OELLERMANN, OR .
JOURNAL OF GRAPH THEORY, 1987, 11 (02) :235-249
[10]   HIGHLY IRREGULAR DIGRAPHS [J].
ALAVI, Y ;
LIU, JQ ;
WANG, JF .
DISCRETE MATHEMATICS, 1993, 111 (1-3) :3-10