Generalized stepwise irregular graphs: graph operations and construction of 3-SI graphs

Document Type : Full Length Article

Authors

Department of Mathematics and Computer Sciences, Hakim Sabzevari University, Sabzevar, Iran.

Abstract

Generalized stepwise irregular (GSI) graphs are graphs in which the degree difference between every pair of adjacent vertices is a positive constant. Specifically, a graph G is called a k-stepwise irregular ( k-SI) graph if |dG(u)-dG(v)|=k for each edge uv∈E(G). In this paper, we examine the behavior of GSI graphs under certain graph operations, including sum, corona product, complement, subdivision, line graph, and vertex deletion. An Infinite family of 3-SI graphs with a given cyclomatic number and distinct cycles is constructed. Further, a lower bound on the size of the unicyclic 3-SI graphs is proposed.

Graphical Abstract

Generalized stepwise irregular graphs: graph operations and construction of 3-SI graphs

Keywords

Main Subjects


[1] H. Abdo, N. Cohen, D. Dimitrov, Graphs with maximal irregularity, Filomat 28 (2014) 1315–1322.
https://doi.org/10.2298/FIL1405315A
[2] H. Abdo, D. Dimitrov, I. Gutman, Graph irregularity and its measures, Appl. Math. Comput. 357
(2019) 317–324. https://doi.org/10.1016/j.amc.2019.04.061
[3] M. O. Albertson, Irregularity of a graph, Ars Combin. 46 (1997) 219–225. https:// doi.org /
10.1021/ja9621760
[4] A. Ali, G. Chartrand, P. Zhang, Irregularity in graphs, Springer, Cham, 2021. https:// doi.org/
10.1007/ 978-3-030-67993-9
[5] Y. Alizadeh, S. Klavžar, J. Langari, Extremal results on k-SI graphs, Appl. Math. Comput. 514 (2026)
129818. https://doi.org/10.1016/j.amc.2024.129818
[6] Y. Alizadeh, S. Klavžar, Z. Molaee, Generalized stepwise transmission irregular graphs, Filomat 38
(2024) 5875–5883. https://doi.org/10.2298/FIL2406875A
[7] M. Azari, N. Dehgardi, T. Došlić, Lower bounds on the irregularity of trees and unicyclic graphs,
Discrete Appl. Math. 324 (2023) 136–144.
[8] S. Bera, P. Paul, Properties of stepwise irregular graphs, arXiv:1809.03297 [math.CO], 2018.
https://doi.org/10.48550/arXiv.1809.03297
[9] L. Buyantogtokh, E. Azjargal, B. Horoldagva, Sh. Dorjsembe, D. Adiyanyam, On the maximum size of stepwise irregular graphs, Appl. Math. Comput. 392 (2021) Article 125683.
https://doi.org/10.1016/j.amc.2020.125683
[10] S. Das, U. Mishra, and Sh. Rai, On two-stepwise irregular graphs, Sci. Iranica 30(3) (2023) 1049–1057.
https://doi.org/10.24200/sci.2022.57725.5388
[11] T. Došlić, Vertex-weighted Wiener polynomials for composite graphs, Ars Math. Contemp. 1 (2008)
66–80. https://doi.org/10.26493/1855-3974.1.66
[12] I. Gutman, Stepwise irregular graphs, Appl. Math. Comput. 325 (2018) 234–238.
https://doi.org/10.1016/j.amc.2017.12.042
[13] I. Gutman, B. Furtula, Z. K. Vukićević, G. Popivoda, On Zagreb indices and coindices, MATCH
Commun. Math. Comput. Chem. 74 (2015) 5–16. https://doi.org/10.46793/match.74-1.005G
[14] F. Harary, Graph theory, Addison-Wesley, Reading, MA, 1969. https:// doi.org/ 10.1201/
9780429496768
[15] M. Randić, Characterization of molecular branching, J. Am. Chem. Soc. 97 (1975) 6609–6615.
https://doi.org/10.1021/ja00856a001
[16] T. Reti, R. Sharafdini, A. Dregelyi-Kiss, and H. Haghbin, Graph irregularity indices used as
molecular descriptors in QSPR studies, MATCH Commun. Math. Comput. Chem. 79 (2018) 509–524.
https://doi.org/10.46793/match.79-2.509R
Volume 11, Issue 1
March 2026
Pages 33-42
  • Receive Date: 19 August 2025
  • Revise Date: 11 November 2025
  • Accept Date: 15 November 2025
  • First Publish Date: 30 January 2026
  • Publish Date: 01 March 2026