Previous |  Up |  Next

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: 2024-10-04
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
.

Files

Files Size Format View
CzechMathJ_72-2022-3_8.pdf 262.8Kb application/pdf View/Open
Back to standard record
Partner of
EuDML logo