DEGREE-BASED INVARIANTS OF MYCIELSKI CONSTRUCTION: IRREGULARITY, TOTAL IRREGULARITY, VARIANCE

Year 2019, Volume: 37 Issue: 3, 747 - 754, 01.09.2020

Zeynep Nihan Berberler

Abstract

The degree-based graph invariants are parameters defined by degrees of vertices. A graph is regular if all of its vertices have the same degree. Otherwise a graph is irregular. To measure how irregular a graph is, graph topological indices were proposed including the irregularity of a graph, total irregularity of a graph, and the variance of the vertex degrees. In this paper, the above mentioned irregularity measures for Mycielski constructions of any underlying graph are considered and exact formulae are derived.

Keywords

: Irregularity of a graph, total irregularity of a graph, variance of the vertex degrees, Mycielski construction

References

• [1] Albertson M.O., (1997) The irregularity of a graph, Ars Combin. 46, 219–225.
• [2] Abdo H., Brandt S., Dimitrov D., (2014) The total irregularity of a graph, Discrete Math. Theor. Comput. Sci. 16(1), 201-206.
• [3] Bell F. K., (1992) A note on the irregularity of graphs, Linear Algebra Appl. 161, 45–54.
• [4] Berberler Z. N., (2019) On computing the irregularity of R-corona product types of graphs, Util. Math. to appear.
• [5] Berberler Z. N., (2019) Total Irregularity of Indu-Bala Product of Graphs, APJES 7(1), 52-55.
• [6] Criado R., Flores J., García del Amo A., Romance M., (2014) Centralities of a network and its line graph: an analytical comparison by means of their irregularity, Int. J. Comput. Math. 91(2), 304-314.
• [7] Estrada E., (2010) Randić index, irregularity and complex biomolecular networks, Acta Chim. Slov. 57, 597–603.
• [8] Hansen P., Mélot H., (2005) Variable neighborhood search for extremal graphs. 9. Bounding the irregularity of a graph, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 69, 253-264.
• [9] You L.H., Yang J.S., You Z.F., (2014) The maximal total irregularity of unicyclic graphs, Ars Comb. 114, 153–160.
• [10] You L.H., Yang J.S., Zhu Y.X., You Z.F., (2014) The maximal total irregularity of bicyclic graphs, J. Appl. Math. Article ID 785084, http://dx.doi.org/10.1155/2014/785084.
• [11] Zhu Y., You L., Yang J., (2016) The minimal total irregularity of some classes of graphs, Filomat 30(5), 1203-1211.
• [12] Dimitrov D., Škrekovski R., (2015) Comparing the irregularity and the total irregularity of graphs, Ars Math. Contemp. 9, 45–50.
• [13] Zhou B., (2008) On irregularity of graphs, Ars Combin. 88, 55-64.
• [14] Abdo H., Dimitrov D., (2014) The irregularity of graphs under graph operations, Discuss. Math. Graph Theo. 34(2), 263–278.
• [15] Abdo H., Dimitrov D., (2014) The total irregularity of graphs under graph operations, Miskolc Math. Notes 15, 3–17.
• [16] Abdo H., Dimitrov D., (2015) The Total Irregularity of Some Composite Graphs, Int. J. Comput. Appl. 122(21), 1-9.
• [17] Abdo H., Dimitrov D., Gao W., (2017) On the irregularity of some molecular structures, Can. J. Chem. 95(2), 174-183.
• [18] Abdo H., Cohen N., Dimitrov D., (2014) Graphs with maximal irregularity, Filomat 28(7), 1315-1322.
• [19] Gutman I., Hansen P., Mélot H., (2005) Variable neighborhood search for extremal graphs. 10. Comparison of irregularity indices for chemical trees, J. Chem. Inf. Model. 45, 222-230.
• [20] Henning M.A., Rautenbach D., (2007) On the irregularity of bipartite graphs, Discrete Math. 307, 1467-1472.
• [21] Albertson M.O., Berman D., (1991) Ramsey graphs without repeated degrees, Congr. Numer. 83, 91–96.
• [22] Tavakoli M., Rahbarnia F., Ashrafi A.R., (2014) Some new results on irregularity of graphs, J. Appl. Math. Inform. 32, 675-685.
• [23] Luo W., Zhou B., (2010) On the irregularity of trees and unicyclic graphs with given matching number, Util. Math. 83, 141-147.
• [24] Mycielski J., (1955) Sur le coloriage des graphs, Colloq. Math. 3, 161–162.
• [25] Gutman I., Trinajstić N., (1972) Graph theory and molecular orbitals. Total  - electron energy of alternant hydrocarbons, Chem. Phys. Lett. 17, 535-538.