The irregularity of graphs under graph operations
Hosam Abdo ; Darko Dimitrov
Discussiones Mathematicae Graph Theory, Tome 34 (2014), p. 263-278 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

The irregularity of a simple undirected graph G was defined by Albertson [5] as irr(G) = ∑uv∈E(G) |dG(u) − dG(v)|, where dG(u) denotes the degree of a vertex u ∈ V (G). In this paper we consider the irregularity of graphs under several graph operations including join, Cartesian product, direct product, strong product, corona product, lexicographic product, disjunction and sym- metric difference. We give exact expressions or (sharp) upper bounds on the irregularity of graphs under the above mentioned operations

Publié le : 2014-01-01
EUDML-ID : urn:eudml:doc:268138 
@article{bwmeta1.element.doi-10_7151_dmgt_1733,
     author = {Hosam Abdo and Darko Dimitrov},
     title = {The irregularity of graphs under graph operations},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {34},
     year = {2014},
     pages = {263-278},
     zbl = {1290.05062},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1733}
}

Hosam Abdo; Darko Dimitrov. The irregularity of graphs under graph operations. Discussiones Mathematicae Graph Theory, Tome 34 (2014) pp. 263-278. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1733/

[1] H. Abdo and D. Dimitrov, Total irregularity of a graph, (2012) a manuscript. arxiv.org/abs/1207.5267 | Zbl 1313.05313

[2] Y. Alavi, A. Boals, G. Chartrand, P. Erdös and O.R. Oellermann, k-path irregular graphs, Congr. Numer. 65 (1988) 201-210. | Zbl 0669.05046

[3] Y. Alavi, G. Chartrand, F.R.K. Chung, P. Erdös, R.L. Graham and O.R. Oeller- mann, Highly irregular graphs, J. Graph Theory 11 (1987) 235-249. doi:10.1002/jgt.3190110214[Crossref]

[4] Y. Alavi, J. Liu and J. Wang, Highly irregular digraphs, Discrete Math. 111 (1993) 3-10. doi:10.1016/0012-365X(93)90134-F[Crossref]

[5] M.O. Albertson, The irregularity of a graph, Ars Combin. 46 (1997) 219-225. | Zbl 0933.05073

[6] M.O. Albertson and D. Berman, Ramsey graphs without repeated degrees, Congr. Numer. 83 (1991) 91-96. | Zbl 0765.05073

[7] F.K. Bell, A note on the irregularity of graphs, Linear Algebra Appl. 161 (1992) 45-54. doi:10.1016/0024-3795(92)90004-T[Crossref]

[8] F.K. Bell, On the maximal index of connected graphs, Linear Algebra Appl. 144 (1991) 135-151. doi:10.1016/0024-3795(91)90067-7[Crossref]

[9] G. Chartrand, P. Erd˝os and O.R. Oellermann, How to define an irregular graph, College Math. J. 19 (1988) 36-42. doi:10.2307/2686701[Crossref] | Zbl 0995.05516

[10] G. Chartrand, K.S. Holbert, O.R. Oellermann and H.C. Swart, F-degrees in graphs, Ars Combin. 24 (1987) 133-148. | Zbl 0643.05055

[11] G. Chen, P. Erd˝os, C. Rousseau and R. Schelp, Ramsey problems involving degrees in edge-colored complete graphs of vertices belonging to monochromatic subgraphs, European J. Combin. 14 (1993) 183-189. doi:10.1006/eujc.1993.1023[Crossref]

[12] L. Collatz and U. Sinogowitz, Spektren endlicher Graphen, Abh. Math. Semin. Univ. Hamburg 21 (1957) 63-77. doi:10.1007/BF02941924[Crossref] | Zbl 0077.36704

[13] D. Cvetkovi´c and P. Rowlinson, On connected graphs with maximal index , Publica- tions de l’Institut Mathematique Beograd 44 (1988) 29-34.

[14] K.C. Das and I. Gutman, Some properties of the second Zagreb index , MATCH Commun. Math. Comput. Chem. 52 (2004) 103-112. | Zbl 1077.05094

[15] T. Došli´c, B. Furtula, A. Graovac, I. Gutman, S. Moradi and Z. Yarahmadi, On vertex degree based molecular structure descriptors, MATCH Commun. Math. Comput. Chem. 66 (2011) 613-626. | Zbl 1265.05144

[16] G.H. Fath-Tabar, Old and new Zagreb indices of graphs, MATCH Commun. Math. Comput. Chem. 65 (2011) 79-84.

[17] I. Gutman and K.C. Das, The first Zagreb index 30 years after , MATCH Commun. Math. Comput. Chem. 50 (2004) 83-92. | Zbl 1053.05115

[18] I. Gutman, P. Hansen and H. M´elot, Variable neighborhood search for extremal graphs. 10. Comparison of irregularity indices for chemical trees, J. Chem. Inf. Model. 45 (2005) 222-230. doi:10.1021/ci0342775[Crossref]

[19] R. Hammack, W. Imrich and S. Klavˇzar, Handbook of Product Graphs (CRC Press, Boca Raton, FL, 2011). | Zbl 1283.05001

[20] P. Hansen and H.M´elot, Variable neighborhood search for extremal graphs. 9. Bounding the irregularity of a graph, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 69 (2005) 253-264. | Zbl 1095.05019

[21] M.A. Henning and D. Rautenbach, On the irregularity of bipartite graphs, Discrete Math. 307 (2007) 1467-1472.[WoS] | Zbl 1126.05060

[22] D.E. Jackson and R. Entringer, Totally segregated graphs, Congr. Numer. 55 (1986) 159-165. | Zbl 0633.05060

[23] D.J. Miller, The categorical product of graphs, Canad. J. Math. 20 (1968) 1511-1521. doi:10.4153/CJM-1968-151-x[Crossref] | Zbl 0167.21902

[24] S. Nikoli´c, G. Kovaˇcevi´c, A. Miliˇcevi´c and N. Trinajsti´c, The Zagreb indices 30 years after , Croat. Chem. Acta 76 (2003) 113-124.

[25] N. Trinajsti´c, S. Nikoli´c, A. Miliˇcevi´c and I. Gutman, On Zagreb indices, Kem. Ind. 59 (2010) 577-589.

[26] P.M. Weichsel, The Kronecker product of graphs, Proc. Amer. Math. Soc. 13 (1962) 47-52. doi:10.4153/CJM-1968-151-x[Crossref] | Zbl 0102.38801

[27] V. Yegnanarayanan, P.R. Thiripurasundari and T. Padmavathy, On some graph operations and related applications, Electron. Notes Discrete Math. 33 (2009) 123-130. doi:10.1016/j.endm.2009.03.018[Crossref] | Zbl 1267.05226

[28] B. Zhou, Remarks on Zagreb indices, MATCH Commun. Math. Comput. Chem. 57 (2007) 591-596. | Zbl 1141.05027

[29] B. Zhou and I. Gutman, Further properties of Zagreb indices, MATCH Commun. Math. Comput. Chem 54 (2005) 233-239.