Article
| Title: | The extremal irregularity of connected graphs with given number of pendant vertices (English) |
| Author: | Liu, Xiaoqian |
| Author: | Chen, Xiaodan |
| Author: | Hu, Junli |
| Author: | Zhu, Qiuyun |
| Language: | English |
| Journal: | Czechoslovak Mathematical Journal |
| ISSN: | 0011-4642 (print) |
| ISSN: | 1572-9141 (online) |
| Volume: | 72 |
| Issue: | 3 |
| Year: | 2022 |
| Pages: | 735-746 |
| Summary lang: | English |
| . | |
| Category: | math |
| . | |
| 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. (English) |
| Keyword: | graph irregularity |
| Keyword: | connected graph |
| Keyword: | pendant vertex |
| Keyword: | extremal graph |
| MSC: | 05C07 |
| MSC: | 05C35 |
| idZBL: | Zbl 07584098 |
| idMR: | MR4467938 |
| DOI: | 10.21136/CMJ.2022.0125-21 |
| . | |
| Date available: | 2022-08-22T08:19:28Z |
| Last updated: | 2022-12-27 |
| Stable URL: | http://hdl.handle.net/10338.dmlcz/150613 |
| . | |
| Reference: | [1] Abdo, H., Cohen, N., Dimitrov, D.: Graphs with maximal irregularity.Filomat 28 (2014), 1315-1322. Zbl 1464.05048, MR 3360039, 10.2298/FIL1407315A |
| Reference: | [2] Abdo, H., Dimitrov, D.: The irregularity of graphs under graph operations.Discuss. Math., Graph Theory 34 (2014), 263-278. Zbl 1290.05062, MR 3194036, 10.7151/dmgt.1733 |
| Reference: | [3] Albertson, M. O.: The irregularity of a graph.Ars Comb. 46 (1997), 219-225. Zbl 0933.05073, MR 1470801 |
| Reference: | [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. Zbl 0765.05073, MR 1152082 |
| Reference: | [5] Chen, X., Hou, Y., Lin, F.: Some new spectral bounds for graph irregularity.Appl. Math. Comput. 320 (2018), 331-340. Zbl 1426.05088, MR 3722748, 10.1016/j.amc.2017.09.038 |
| Reference: | [6] Dimitrov, D., Réti, T.: Graphs with equal irregularity indices.Acta Polytech. Hung. 11 (2014), 41-57. |
| Reference: | [7] Dimitrov, D., Škrekovski, R.: Comparing the irregularity and the total irregularity of graphs.Ars Math. Contemp. 9 (2015), 45-50. Zbl 1332.05037, MR 3377090, 10.26493/1855-3974.341.bab |
| Reference: | [8] Fath-Tabar, G. H.: Old and new Zagreb indices of graphs.MATCH Commun. Math. Comput. Chem. 65 (2011), 79-84. Zbl 1265.05146, MR 2797217 |
| Reference: | [9] Goldberg, F.: A spectral bound for graph irregularity.Czech. Math. J. 65 (2015), 375-379. Zbl 1349.05181, MR 3360433, 10.1007/s10587-015-0182-5 |
| Reference: | [10] Gutman, I.: Irregularity of molecular graphs.Kragujevac J. Sci. 38 (2016), 71-81. 10.5937/KgJSci1638071G |
| Reference: | [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. 10.1021/ci0342775 |
| Reference: | [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. Zbl 1095.05019, MR 2193452 |
| Reference: | [13] Henning, M. A., Rautenbach, D.: On the irregularity of bipartite graphs.Discrete Math. 307 (2007), 1467-1472. Zbl 1126.05060, MR 2311120, 10.1016/j.disc.2006.09.038 |
| Reference: | [14] Liu, Y., Li, J.: On the irregularity of cacti.Ars Comb. 143 (2019), 77-89. Zbl 1449.05052, MR 3967495 |
| Reference: | [15] Luo, W., Zhou, B.: On the irregularity of trees and unicyclic graphs with given matching number.Util. Math. 83 (2010), 141-147. Zbl 1242.05223, MR 2742282 |
| Reference: | [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. Zbl 1338.05049, 10.1016/j.endm.2013.11.026 |
| Reference: | [17] Rautenbach, D., Volkmann, L.: How local irregularity gets global in a graph.J. Graph Theory 41 (2002), 18-23. Zbl 1019.05034, MR 1919164, 10.1002/jgt.10043 |
| Reference: | [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. Zbl 1428.05086, MR 3886406, 10.1016/j.amc.2018.10.010 |
| Reference: | [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. Zbl 1472.92338, MR 3754230 |
| Reference: | [20] Tavakoli, M., Rahbarnia, F., Mirzavaziri, M., Ashrafi, A. R., Gutman, I.: Extremely irregular graphs.Kragujevac J. Math. 37 (2013), 135-139. Zbl 1299.05060, MR 3073703 |
| Reference: | [21] Vukičević, D., Gašperov, M.: Bond additive modeling 1. Adriatic indices.Croat. Chem. Acta 83 (2010), 243-260. |
| Reference: | [22] Zhou, B., Luo, W.: On irregularity of graphs.Ars Comb. 88 (2008), 55-64. Zbl 1224.05110, MR 2426406 |
| . |
Fulltext not available (moving wall 24 months)
Search
Partner of
