The extremal irregularity of connected graphs with given number of pendant vertices

Xiaoqian Liu; Xiaodan Chen; Junli Hu; Qiuyun Zhu

Czechoslovak Mathematical Journal (2022)

  • Volume: 72, Issue: 3, page 735-746
  • ISSN: 0011-4642

Abstract

top
The irregularity of a graph G = ( V , E ) is defined as the sum of imbalances | d u - d v | over all edges u v ∈ 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 ≤ p ≤ n - 1 ), and characterize the corresponding extremal graphs.

How to cite

top

Liu, Xiaoqian, et al. "The extremal irregularity of connected graphs with given number of pendant vertices." Czechoslovak Mathematical Journal 72.3 (2022): 735-746. <http://eudml.org/doc/298405>.

@article{Liu2022,
abstract = {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\le p \le n-1$), and characterize the corresponding extremal graphs.},
author = {Liu, Xiaoqian, Chen, Xiaodan, Hu, Junli, Zhu, Qiuyun},
journal = {Czechoslovak Mathematical Journal},
keywords = {graph irregularity; connected graph; pendant vertex; extremal graph},
language = {eng},
number = {3},
pages = {735-746},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {The extremal irregularity of connected graphs with given number of pendant vertices},
url = {http://eudml.org/doc/298405},
volume = {72},
year = {2022},
}

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
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 72
IS - 3
SP - 735
EP - 746
AB - 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\le p \le n-1$), and characterize the corresponding extremal graphs.
LA - eng
KW - graph irregularity; connected graph; pendant vertex; extremal graph
UR - http://eudml.org/doc/298405
ER -

References

top
  1. Abdo, H., Cohen, N., Dimitrov, D., 10.2298/FIL1407315A, Filomat 28 (2014), 1315-1322. (2014) Zbl1464.05048MR3360039DOI10.2298/FIL1407315A
  2. Abdo, H., Dimitrov, D., 10.7151/dmgt.1733, Discuss. Math., Graph Theory 34 (2014), 263-278. (2014) Zbl1290.05062MR3194036DOI10.7151/dmgt.1733
  3. Albertson, M. O., The irregularity of a graph, Ars Comb. 46 (1997), 219-225. (1997) Zbl0933.05073MR1470801
  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. (1991) Zbl0765.05073MR1152082
  5. Chen, X., Hou, Y., Lin, F., 10.1016/j.amc.2017.09.038, Appl. Math. Comput. 320 (2018), 331-340. (2018) Zbl1426.05088MR3722748DOI10.1016/j.amc.2017.09.038
  6. Dimitrov, D., Réti, T., Graphs with equal irregularity indices, Acta Polytech. Hung. 11 (2014), 41-57. (2014) 
  7. Dimitrov, D., Škrekovski, R., 10.26493/1855-3974.341.bab, Ars Math. Contemp. 9 (2015), 45-50. (2015) Zbl1332.05037MR3377090DOI10.26493/1855-3974.341.bab
  8. Fath-Tabar, G. H., Old and new Zagreb indices of graphs, MATCH Commun. Math. Comput. Chem. 65 (2011), 79-84. (2011) Zbl1265.05146MR2797217
  9. Goldberg, F., 10.1007/s10587-015-0182-5, Czech. Math. J. 65 (2015), 375-379. (2015) Zbl1349.05181MR3360433DOI10.1007/s10587-015-0182-5
  10. Gutman, I., 10.5937/KgJSci1638071G, Kragujevac J. Sci. 38 (2016), 71-81. (2016) DOI10.5937/KgJSci1638071G
  11. Gutman, I., Hansen, P., Mélot, H., 10.1021/ci0342775, J. Chem. Inf. Model. 45 (2005), 222-230. (2005) DOI10.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. (2005) Zbl1095.05019MR2193452
  13. Henning, M. A., Rautenbach, D., 10.1016/j.disc.2006.09.038, Discrete Math. 307 (2007), 1467-1472. (2007) Zbl1126.05060MR2311120DOI10.1016/j.disc.2006.09.038
  14. Liu, Y., Li, J., On the irregularity of cacti, Ars Comb. 143 (2019), 77-89. (2019) Zbl1449.05052MR3967495
  15. Luo, W., Zhou, B., On the irregularity of trees and unicyclic graphs with given matching number, Util. Math. 83 (2010), 141-147. (2010) Zbl1242.05223MR2742282
  16. Nasiri, R., Fath-Tabar, G. H., 10.1016/j.endm.2013.11.026, Extended Abstracts of the 5th Conference on Algebraic Combinatorics and Graph Theory (FCC) Electronic Notes in Discrete Mathematics 45. Elsevier, Amsterdam (2014), 133-140. (2014) Zbl1338.05049DOI10.1016/j.endm.2013.11.026
  17. Rautenbach, D., Volkmann, L., 10.1002/jgt.10043, J. Graph Theory 41 (2002), 18-23. (2002) Zbl1019.05034MR1919164DOI10.1002/jgt.10043
  18. Réti, T., 10.1016/j.amc.2018.10.010, Appl. Math. Comput. 344-345 (2019), 107-115. (2019) Zbl1428.05086MR3886406DOI10.1016/j.amc.2018.10.010
  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. (2018) Zbl1472.92338MR3754230
  20. Tavakoli, M., Rahbarnia, F., Mirzavaziri, M., Ashrafi, A. R., Gutman, I., Extremely irregular graphs, Kragujevac J. Math. 37 (2013), 135-139. (2013) Zbl1299.05060MR3073703
  21. Vukičević, D., Gašperov, M., Bond additive modeling 1. Adriatic indices, Croat. Chem. Acta 83 (2010), 243-260. (2010) 
  22. Zhou, B., Luo, W., On irregularity of graphs, Ars Comb. 88 (2008), 55-64. (2008) Zbl1224.05110MR2426406

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.