Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
graph irregularity; connected graph; pendant vertex; extremal graph
graph irregularity; connected graph; pendant vertex; extremal graph
Summary:
The irregularity of a graph $G=(V, E)$ is defined as the sum of imbalances $|d_u-d_v|$ over all edges $uv\in E$, where $d_u$ denotes the degree of the vertex $u$ in $G$. This graph invariant, introduced by Albertson in 1997, is a measure of the defect of regularity of a graph. In this paper, we completely determine the extremal values of the irregularity of connected graphs with $n$ vertices and $p$ pendant vertices ($1\leq p \leq n-1$), and characterize the corresponding extremal graphs.
References:
[1] Abdo, H., Cohen, N., Dimitrov, D.: Graphs with maximal irregularity. Filomat 28 (2014), 1315-1322. DOI 10.2298/FIL1407315A | MR 3360039 | Zbl 1464.05048
[2] Abdo, H., Dimitrov, D.: The irregularity of graphs under graph operations. Discuss. Math., Graph Theory 34 (2014), 263-278. DOI 10.7151/dmgt.1733 | MR 3194036 | Zbl 1290.05062
[3] Albertson, M. O.: The irregularity of a graph. Ars Comb. 46 (1997), 219-225. MR 1470801 | Zbl 0933.05073
[4] Albertson, M. O., Berman, D. M.: Ramsey graphs without repeated degrees. Proceedings of the Twenty-Second Southeastern Conference on Combinatorics, Graph Theory, and Computing Congressus Numerantium 83. Utilitas Mathematica Publishing, Winnipeg (1991), 91-96. MR 1152082 | Zbl 0765.05073
[5] Chen, X., Hou, Y., Lin, F.: Some new spectral bounds for graph irregularity. Appl. Math. Comput. 320 (2018), 331-340. DOI 10.1016/j.amc.2017.09.038 | MR 3722748 | Zbl 1426.05088
[6] Dimitrov, D., Réti, T.: Graphs with equal irregularity indices. Acta Polytech. Hung. 11 (2014), 41-57.
[7] Dimitrov, D., Škrekovski, R.: Comparing the irregularity and the total irregularity of graphs. Ars Math. Contemp. 9 (2015), 45-50. DOI 10.26493/1855-3974.341.bab | MR 3377090 | Zbl 1332.05037
[8] Fath-Tabar, G. H.: Old and new Zagreb indices of graphs. MATCH Commun. Math. Comput. Chem. 65 (2011), 79-84. MR 2797217 | Zbl 1265.05146
[9] Goldberg, F.: A spectral bound for graph irregularity. Czech. Math. J. 65 (2015), 375-379. DOI 10.1007/s10587-015-0182-5 | MR 3360433 | Zbl 1349.05181
[10] Gutman, I.: Irregularity of molecular graphs. Kragujevac J. Sci. 38 (2016), 71-81. DOI 10.5937/KgJSci1638071G
[11] Gutman, I., Hansen, P., Mélot, H.: 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
[12] Hansen, P., Mélot, H.: Variable neighborhood search for extremal graphs 9. Bounding the irregularity of a graph. Graphs and Discovery DIMACS Series in Discrete Mathematics and Theoretical Computer Science 69. AMS, Providence (2005), 253-264. MR 2193452 | Zbl 1095.05019
[13] Henning, M. A., Rautenbach, D.: On the irregularity of bipartite graphs. Discrete Math. 307 (2007), 1467-1472. DOI 10.1016/j.disc.2006.09.038 | MR 2311120 | Zbl 1126.05060
[14] Liu, Y., Li, J.: On the irregularity of cacti. Ars Comb. 143 (2019), 77-89. MR 3967495 | Zbl 1449.05052
[15] Luo, W., Zhou, B.: On the irregularity of trees and unicyclic graphs with given matching number. Util. Math. 83 (2010), 141-147. MR 2742282 | Zbl 1242.05223
[16] Nasiri, R., Fath-Tabar, G. H.: The second minimum of the irregularity of graphs. Extended Abstracts of the 5th Conference on Algebraic Combinatorics and Graph Theory (FCC) Electronic Notes in Discrete Mathematics 45. Elsevier, Amsterdam (2014), 133-140. DOI 10.1016/j.endm.2013.11.026 | Zbl 1338.05049
[17] Rautenbach, D., Volkmann, L.: How local irregularity gets global in a graph. J. Graph Theory 41 (2002), 18-23. DOI 10.1002/jgt.10043 | MR 1919164 | Zbl 1019.05034
[18] Réti, T.: On some properties of graph irregularity indices with a particular regard to the $\sigma$-index. Appl. Math. Comput. 344-345 (2019), 107-115. DOI 10.1016/j.amc.2018.10.010 | MR 3886406 | Zbl 1428.05086
[19] Réti, T., Sharafdini, R., Drégelyi-Kiss, Á., Haghbin, H.: Graph irregularity indices used as molecular descriptors in QSPR studies. MATCH Commun. Math. Comput. Chem. 79 (2018), 509-524. MR 3754230 | Zbl 1472.92338
[20] Tavakoli, M., Rahbarnia, F., Mirzavaziri, M., Ashrafi, A. R., Gutman, I.: Extremely irregular graphs. Kragujevac J. Math. 37 (2013), 135-139. MR 3073703 | Zbl 1299.05060
[21] Vukičević, D., Gašperov, M.: Bond additive modeling 1. Adriatic indices. Croat. Chem. Acta 83 (2010), 243-260.
[22] Zhou, B., Luo, W.: On irregularity of graphs. Ars Comb. 88 (2008), 55-64. MR 2426406 | Zbl 1224.05110
Search
Partner of
