On size of $k$-stepwise irregular graphs and their degree based indices

Articles in Press

Document Type : Original paper

Authors

1 Department of Mathematics, Hakim Sabzevari University, Sabzevar, Iran

2 Faculty of Mathematics and Physics, University of Ljubljana, Slovenia

3 Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia

4 Faculty of Natural Sciences and Mathematics, University of Maribor, Slovenia

Abstract

A graph $G$ is $k$-stepwise irregular if $|d_G(u)-d_G(v)|= k$ holds for every edge $uv$ of $G$. It is proved that for such a graph $m(G) \leq (n(G)^2 - k^2)/4$ holds, where the equality holds if and only if $G\cong K_{\frac{n(G)+k}{2},\frac{n(G)-k}{2}}$. Using this result, sharp lower and upper bounds are derived for Zagreb (co)indices, the Sombor index, and the Randi'c index of $k$-stepwise irregular graphs.

Keywords

Main Subjects

References

[1] H. Abdo, D. Dimitrov, and I. Gutman, Graph irregularity and its measures, Appl. Math. Comput. 357 (2019), 317–324.
https://doi.org/10.1016/j.amc.2019.04.013
[2] D. Adiyanyam, E. Azjargal, and L. Buyantogtokh, Bond incident degree indices of stepwise irregular graphs, AIMS Math. 7 (2022), no. 5, 8685–8700. https://doi.org/10.3934/math.2022485
[3] S. Ahmad and K.Ch. Das, A complete solution for maximizing the general Sombor index of chemical trees with given number of pendant vertices, Appl. Math. Comput. 505 (2025), 129532, https://doi.org/10.1016/j.amc.2025.129532
[4] N. Akhter and A.N. Al-Hossain Ahmad, Stepwise irregular graphs and their metric-based resolvability parameters, Math. Prob. Eng. 2022 (2022), no. 1, 3752298, https://doi.org/10.1155/2022/3752298
[5] S. Al-Yakoob and D. Stevanović, On stepwise transmission irregular graphs, Appl. Math. Comput. 413 (2022), 126607.
https://doi.org/10.1016/j.amc.2021.126607
[6] M.O. Albertson, The irregularity of a graph, Ars Combin. 46 (1997), 219–226.
[7] A. Ali, G. Chartrand, and P. Zhang, Irregularity in Graphs, Springer, 2021.
[8] Y. Alizadeh, S. Klavžar, and J. Langari, Extremal results on $k$-stepwise irregular graphs, Appl. Math. Comput. 514
(2026), 129818.  https://doi.org/10.1016/j.amc.2025.129818
[9] Y. Alizadeh, S. Klavžar, and Z. Molaee, Generalized stepwise transmission irregular graphs, Filomat 38 (2024), no. 16, 5875–5883. https://doi.org/10.48550/arXiv.2306.05699
[10] G. Arizmendi and D. Huerta, Energy of a graph and Randi´c index of subgraphs, Discrete Appl. Math. 372 (2025), 136–142.  https://doi.org/10.48550/arXiv.2406.03561
[11] A. Bickle and Z. Che, Irregularities of maximal k-degenerate graphs, Discrete Appl. Math. 331 (2023), 70–87. https://doi.org/10.1016/j.dam.2023.01.020
[12] B. Borovićanin, K.C. Das, B. Furtula, and I. Gutman, Bounds for Zagreb indices, MATCH Commun. Math. Comput. Chem. 78 (2017), no. 1, 17–100.
[13] L. Buyantogtokh, E. Azjargal, B. Horoldagva, Sh. Dorjsembe, and D. Adiyanyam, On the maximum size of stepwise irregular graphs, Appl. Math. Comput. 392 (2021), 125683.  https://doi.org/10.1016/j.amc.2020.125683
[14] S. Chanda and R.R. Iyer, On the Sombor index of Sierpi´nski and Mycielskian graphs, Commun. Comb. Optim. 10 (2025), no. 1, 20–56. https://doi.org/10.22049/cco.2023.28681.1669
[15] S. Das, U. Mishra, and S. Rai, On two-stepwise irregular graphs, Sci. Iran. 30 (2023), no. 3, 1049–1057.
https://doi.org/10.24200/sci.2022.57725.5388
[16] A.A. Dobrynin and R. Sharafdini, Stepwise transmission irregular graphs, Appl. Math. Comput. 371 (2020), 124949.
https://doi.org/10.1016/j.amc.2019.124949
[17] T. Došlić, Vertex-weighted Wiener polynomials for composite graphs, Ars Math. Contemp. 1 (2008), no. 1, 66–80.
https://doi.org/10.26493/1855-3974.15.895
[18] I. Gutman, Stepwise irregular graphs, Appl. Math. Comput. 325 (2018), 234–238. https://doi.org/10.1016/j.amc.2017.12.045
[19] I. Gutman, Geometric approach to degree-based topological indices: Sombor indices, MATCH Commun. Math. Comput. Chem. 86 (2021), no. 1, 11–16.
[20] I. Gutman, B. Furtula, Ž.K. Vukićević, and G. Popivoda, On Zagreb indices and coindices, MATCH Commun. Math. Comput. Chem. 74 (2015), no. 1, 5–16.
[21] I. Gutman and N. Trinajstić, Graph theory and molecular orbitals, total $\pi$-electron energy of alternant hydroncarbons, Chem. Phys. Lett. 17 (1972), no. 4, 535–538. https://doi.org/10.1016/0009-2614(72)85099-1
[22] H. Liu, I. Gutman, L. You, and Y. Huang, Sombor index: review of extremal results and bounds, J. Math. Chem. 60 (2022), no. 5, 771–798. https://doi.org/10.1007/s10910-022-01333-y
[23] S. Rabizadeh, M. Habibi, and I. Gutman, Some notes on Sombor index of graphs, MATCH Commun. Math. Comput. Chem. 93 (2025), no. 3, 853–859. https://doi.org/10.46793/match.93-3.853R
[24] M. Randić, Characterization of molecular branching, J. Amer. Chem. Soc. 97 (1975), no. 23, 6609–6615.
[25] E. Swartz and T. Vetrík, General sum-connectivity index and general Randić index of trees with given maximum degree, Discret Math. Lett. 12 (2023), 181–188.
[26] M. Yuan, Limiting distribution for the Randi´c index of a random geometric graph, MATCH Commun. Math. Comput. Chem. 93 (2025), no. 3, 767–789.
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 20 February 2026

Files

Share

How to cite

Statistics