Geodesic
The extremal irregularity of connected graphs with given number of pendant vertices
Czechoslovak Mathematical Journal, Tome 72 (2022) no. 3, pp. 735-746
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.21136/CMJ.2022.0125-21
Classification : 05C07, 05C35
Keywords: graph irregularity; connected graph; pendant vertex; extremal graph 
@article{10_21136_CMJ_2022_0125_21,
     author = {Liu, Xiaoqian and Chen, Xiaodan and Hu, Junli and Zhu, Qiuyun},
     title = {The extremal irregularity of connected graphs with given number of pendant vertices},
     journal = {Czechoslovak Mathematical Journal},
     pages = {735--746},
     year = {2022},
     volume = {72},
     number = {3},
     doi = {10.21136/CMJ.2022.0125-21},
     mrnumber = {4467938},
     zbl = {07584098},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2022.0125-21/}
}
TY  - JOUR
AU  - Liu, Xiaoqian
AU  - Chen, Xiaodan
AU  - Hu, Junli
AU  - Zhu, Qiuyun
TI  - The extremal irregularity of connected graphs with given number of pendant vertices
JO  - Czechoslovak Mathematical Journal
PY  - 2022
SP  - 735
EP  - 746
VL  - 72
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2022.0125-21/
DO  - 10.21136/CMJ.2022.0125-21
LA  - en
ID  - 10_21136_CMJ_2022_0125_21
ER  - 
%0 Journal Article
%A Liu, Xiaoqian
%A Chen, Xiaodan
%A Hu, Junli
%A Zhu, Qiuyun
%T The extremal irregularity of connected graphs with given number of pendant vertices
%J Czechoslovak Mathematical Journal
%D 2022
%P 735-746
%V 72
%N 3
%U http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2022.0125-21/
%R 10.21136/CMJ.2022.0125-21
%G en
%F 10_21136_CMJ_2022_0125_21
Liu, Xiaoqian; Chen, Xiaodan; Hu, Junli; Zhu, Qiuyun. The extremal irregularity of connected graphs with given number of pendant vertices. Czechoslovak Mathematical Journal, Tome 72 (2022) no. 3, pp. 735-746. doi: 10.21136/CMJ.2022.0125-21

[1] Abdo, H., Cohen, N., Dimitrov, D.: Graphs with maximal irregularity. Filomat 28 (2014), 1315-1322. | DOI | MR | JFM

[2] Abdo, H., Dimitrov, D.: The irregularity of graphs under graph operations. Discuss. Math., Graph Theory 34 (2014), 263-278. | DOI | MR | JFM

[3] Albertson, M. O.: The irregularity of a graph. Ars Comb. 46 (1997), 219-225. | MR | JFM

[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 | JFM

[5] Chen, X., Hou, Y., Lin, F.: Some new spectral bounds for graph irregularity. Appl. Math. Comput. 320 (2018), 331-340. | DOI | MR | JFM

[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 | MR | JFM

[8] Fath-Tabar, G. H.: Old and new Zagreb indices of graphs. MATCH Commun. Math. Comput. Chem. 65 (2011), 79-84. | MR | JFM

[9] Goldberg, F.: A spectral bound for graph irregularity. Czech. Math. J. 65 (2015), 375-379. | DOI | MR | JFM

[10] Gutman, I.: Irregularity of molecular graphs. Kragujevac J. Sci. 38 (2016), 71-81. | DOI

[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

[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 | JFM

[13] Henning, M. A., Rautenbach, D.: On the irregularity of bipartite graphs. Discrete Math. 307 (2007), 1467-1472. | DOI | MR | JFM

[14] Liu, Y., Li, J.: On the irregularity of cacti. Ars Comb. 143 (2019), 77-89. | MR | JFM

[15] Luo, W., Zhou, B.: On the irregularity of trees and unicyclic graphs with given matching number. Util. Math. 83 (2010), 141-147. | MR | JFM

[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 | JFM

[17] Rautenbach, D., Volkmann, L.: How local irregularity gets global in a graph. J. Graph Theory 41 (2002), 18-23. | DOI | MR | JFM

[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 | MR | JFM

[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 | JFM

[20] Tavakoli, M., Rahbarnia, F., Mirzavaziri, M., Ashrafi, A. R., Gutman, I.: Extremely irregular graphs. Kragujevac J. Math. 37 (2013), 135-139. | MR | JFM

[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 | JFM

Cité par Sources :