The Irregularity and Total Irregularity of Eulerian Graphs

Document Type : Research Paper


1 Department of Mathematics, University of Qom, Qom, I. R. Iran

2 Department of Pure Mathematics, Faculty of Mathematical Sciences, University of Kashan, Kashan 87317-51167, I. R. Iran


For a graph G, the irregularity and total irregularity of G are defined as irr(G)=∑_(uv∈E(G))〖|d_G (u)-d_G (v)|〗 and irr_t (G)=1/2 ∑_(u,v∈V(G))〖|d_G (u)-d_G (v)|〗, respectively, where d_G (u) is the degree of vertex u. In this paper, we characterize all ‎connected Eulerian graphs with the second minimum irregularity, the second and third minimum total irregularity value, respectively.


Main Subjects

1. H. Abdo, S. Brandt and D. Dimitrov, The total irregularity of a graph, Discrete
Math. Theor. Comput. Sci. 16 (2014) 201−206.
2. H. Abdo, N. Cohen and D. Dimitrov, Graphs with maximal irregularity, Filomat 28
(7) (2014) 1315−1322.
3. H. Abdo and D. Dimitrov, Non-regular graphs with minimal total irregularity,
4. H. Abdo and D. Dimitrov, The total irregularity of graphs under graph operations,
Miskolc Math. Notes 15 (1) (2014) 3−17.
5. H. Abdo and D. Dimitrov, The irregularity of graphs under graph operations,
Discuss. Math. Graph Theory 34 (2) (2014) 263−278.
6. M. O. Albertson, The irregularity of a graph, Ars Comb. 46 (1997) 219−225.
7. A. Astaneh-Asl and G. H. Fath-Tabar, Computing the first and third Zagreb
polynomials of Cartesian product of graphs. Iranian J. Math. Chem. 2 (2) (2011)
8. A.T. Balaban, I. Motoc, D. Bonchev and O. Mekenyan, Topological indices for
structure-activity connection, Topics Curr. Chem. 114 (1983) 21−55.
9. F. K. Bell, A note on the irregularity of graphs, Linear Algebra Appl. 161 (1992)
10. N. L. Biggs, E. K. Lloyd and R. J. Wilson, Graph Theory, Clarendon Press,
Oxford, 1976.
11. J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, MacMillan,
London, 1976.
12. D. Dimitrov and R. Skrekovski, Comparing the irregularity and the total
irregularity of graphs, Ars. Math. Contemp. 9 (2015) 45−50.
13. M. Eliasi, The maximal total irregularity of some connected graphs. Iranian J.
Math. Chem. 6 (2) (2015) 121−128.
14. G. H. Fath-Tabar, Old and new Zagreb index, MATCH Commun. Math. Comput.
Chem. 65 (2011) 79−84.
15. G. H. Fath-Tabar, I. Gutman and R. Nasiri, Extremely irregular trees, Bull. Acad.
Serbe Sci. Arts (Cl. Sci. Math. Natur.) 38 (2013) 1−8.
16. I. Gutman and N. Trinajstić, Graph theory and molecular orbitals total π-electron
energy of alternant hydrocarbons, Chem. Phys. Lett. 17 (1972) 535−538.
17. P. Hansen and H. Melot, Variable neighborhood search for extremal graphs. 9.
bounding the irregularity of a graph, DIMACS Ser. Discrete Math. Theoret.
Comput. Sci. 69 (2005) 253−264.
18. M. A. Henning and D. Rautenbach, On the irregularity of bipartite graphs, Discrete
Math. 307 (2007) 1467−1472.
19. W. Luo and B. Zhou, On the irregularity of trees and unicyclic graphs with given
matching number, Util. Math. 83 (2010) 141−147.
20. R. Nasiri and G. H. Fath-Tabar, The second minimum of the irregularity of graphs,
Electronic. Notes Discrete Math. 45 (2014) 133−140.
21. R. Nasiri, A. Golami, G. H. Fath-Tabar and H. R. Ellahi, Extremely irregular
unicyclic graphs, Kragujevac J. Math. 43 (2) (2019) 281−292.
22. T. Reti and D. Dimitrov, On irregularities of bidegreed graphs, Acta Polytechn.
Hung. 10 (7) (2013) 117−134.
23. M. Tavakoli, F. Rahbarnia and A. R. Ashrafi, Some new results on irregularity of
graphs, J. Appl. Math. Inform. 32 (2014) 675−685.
24. M. Tavakoli, F. Rahbarnia, M. Mirzavaziri, A. R. Ashrafi and I. Gutman,
Extremely irregular graphs, Kragujevac J. Math. 37 (1) (2013) 135−139.
25. R. Todeschini and V. Consonni, Handbook of Molecular Descriptors, Wiley-VCH,
Weinheim, 2000.
26. Z. Yarahmadi and G. H. Fath-Tabar, The Wiener, Szeged, PI, vertex PI, the first
and second Zagreb indices of N-branched phenylacetylenes dendrimers, MATCH
Commun. Math. Comput. Chem. 65 (1) (2011) 201−208.
27. L. You, J. Yang and Z. You, The maximal total irregularity of unicyclic graphs,
Ars Comb. in press.
28. L. You, J. Yang and Z. You, The maximal total irregularity of bicyclic graphs, J.
Appl. Math. (2014) Article ID 785084, 9 pages.
29. B. Zhou and W. Luo, On irregularity of graphs, Ars Combin. 88 (2008) 55−64.