The irregularity of graphs under graph operations

• Autorzy: Hosam Abdo , Darko Dimitrov
• Języki publikacji: EN

Abstrakty

EN

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

Słowa kluczowe

EN

irregularity of graphs; total irregularity of graphs; graph operations; Zagreb indices

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2014
• Tom: 34
• Numer: 2
• Strony: 263-278

Daty

wydano

2014-05-01

online

2014-04-12

Twórcy

autor

Hosam Abdo

• Darko Dimitrov Institut für Informatik, Freie Universität Berlin Takustraße 9, D–14195 Berlin, Germany

autor

Darko Dimitrov

• Institut für Informatik, Freie Universität Berlin Takustraße 9, D–14195 Berlin, Germany

Bibliografia

• [1] H. Abdo and D. Dimitrov, Total irregularity of a graph, (2012) a manuscript. arxiv.org/abs/1207.5267
• [2] Y. Alavi, A. Boals, G. Chartrand, P. Erdös and O.R. Oellermann, k-path irregular graphs, Congr. Numer. 65 (1988) 201-210.
• [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.
• [6] M.O. Albertson and D. Berman, Ramsey graphs without repeated degrees, Congr. Numer. 83 (1991) 91-96.
• [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]
• [10] G. Chartrand, K.S. Holbert, O.R. Oellermann and H.C. Swart, F-degrees in graphs, Ars Combin. 24 (1987) 133-148.
• [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]
• [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.
• [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.
• [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.
• [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).
• [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.
• [21] M.A. Henning and D. Rautenbach, On the irregularity of bipartite graphs, Discrete Math. 307 (2007) 1467-1472.[WoS]
• [22] D.E. Jackson and R. Entringer, Totally segregated graphs, Congr. Numer. 55 (1986) 159-165.
• [23] D.J. Miller, The categorical product of graphs, Canad. J. Math. 20 (1968) 1511-1521. doi:10.4153/CJM-1968-151-x[Crossref]
• [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]
• [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]
• [28] B. Zhou, Remarks on Zagreb indices, MATCH Commun. Math. Comput. Chem. 57 (2007) 591-596.
• [29] B. Zhou and I. Gutman, Further properties of Zagreb indices, MATCH Commun. Math. Comput. Chem 54 (2005) 233-239.

Identyfikatory

DOI

10.7151/dmgt.1733