Document Type : Article

**Authors**

Department of Mathematics, Institute of Science, Banaras Hindu University, Varanasi-221005, Uttar Pradesh, India

**Abstract**

A graph $G$ is called irregular if the degrees of all its vertices are not the same. A graph is said to be \textit{Stepwise Irregular} (SI) if the difference of the degrees of any two adjacent vertices is always 1 (one). This paper deals with \textit{2-Stepwise Irregular} (2-SI) graphs in which the degrees of every pair of adjacent vertices differ by 2. Here we discuss some properties of 2-SI graphs and generalize them for $k$-SI graphs for which the imbalance of every edge is $k$. Besides, we also compute bounds of irregularity for the Albertson index in any 2-SI graph.

**Keywords**

References:

1. Bondy, J. and Murty, U., Graph Theory, 1st Edn., Springer, London (2008).

2. Abdo, H., Dimitrov, D., and Gutman, I. "Graphs with maximal irregularity", Discrete Applied Mathematics, 250, pp. 57-64 (2018).

3. Gao, W., Aamir, M., Iqbal, Z., et al. "On irregularity measures of some dendrimers structures", Mathematics, 7(3), p. 271 (2019).

4. Reti, T. "On some properties of graph irregularity indices with a particular regard to the -index", Applied Mathematics and Computation, 344, pp. 107- 115 (2019).

5. Gutman, I. "Stepwise irregular graphs", Applied Mathematics and Computation, 325, pp. 234-238 (2018).

6. Gutman, I. and Reti, T. "Note on irregular graphs", Bulletin (Academie serbe des sciences et des arts. Classe des sciences mathematiques et naturelles. Sciences mathematiques), 43, pp. 5-16 (2018).

7. Bell, F.K. "A note on the irregularity of graphs", Linear Algebra and Its Applications, 161, pp. 45-54 (1992).

8. Chartrand, G., Erdos, P., and Oellermann, O.R. "How to define an irregular graph", The College Mathematics Journal, 19(1), pp. 36-42 (1988).

9. Gutman, I., Hansen, P., andMelot, H. "Variable neighborhood search for extremal graphs. 10. comparison of irregularity indices for chemical trees", Journal of Chemical Information and Modeling, 45(2), pp. 222 -230 (2005).

10. Dobrynin, A.A. and Sharafdini, R. "Stepwise transmission irregular graphs", Applied Mathematics and Computation, 371, 124949 (2020).

11. Xu, K. and Klavzar, S. "Constructing new families of transmission irregular graphs", Discrete Applied Mathematics, 289, pp. 383-391 (2021).

12. Bezhaev, A.Y. and Dobrynin, A.A. "On quartic transmission irregular graphs", Applied Mathematics and Computation, 399, 126049 (2021).

13. Estrada, E. "Randic index, irregularity and complex biomolecular networks", Acta Chimica Slovenica, 57(3), pp. 597-603 (2010).

14. Balaban, A.T. "Applications of graph theory in chemistry", The Journal for Chemical Information and Computer Scientists, 25(3), pp. 334-343 (1985).

15. Garca-Domenech, R., Galvez, J., Julian-Ortiz, J.V., et al. "Some new trends in chemical graph theory", Chemical Reviews, 108(3), pp. 1127-1169 (2008).

16. Burch, K.J. "Chapter 8: Chemical applications of graph theory", in Mathematical Physics in Theoretical Chemistry (S. Blinder and J. House, eds.), Developments in Physical & Theoretical Chemistry, Elsevier, pp. 261-294 (2019).

17. Gutman, I. and Trinajstic, N. "Graph theory and molecular orbitals. Total '-electron energy of alternant hydrocarbons", Chemical Physics Letters, 17(4), pp. 535-538 (1972).

18. Das, S. and Rai, S. "Degree-based topological descriptors of type 3 rectangular hex-derived networks", Bulletin of the Institute of Combinatorics and its Applications, 95, pp. 21-37 (2022).

19. Dobrynin, A.A. and Kochetova, A.A. "Degree distance of a graph: A degree analog of the wiener index", Journal of Chemical Information and Computer Sciences, 34(5), pp. 1082-1086 (1994).

20. Khadikar, P.V. "On a novel structural descriptor PI", National Academy Science Letters, 23, pp. 113-118 (2000).

21. Das, S. and Rai, S. "Topological characterization of the third type of triangular hex-derived networks", Scientific Annals of Computer Science, 31(2), pp. 145- 161 (2021).

22. Das, S. and Kumar, V. "Investigation of closed derivation formulas for GQ and QG indices of a graph via M-polynomial", Iranian Journal of Mathematical Chemistry, 13(2), pp. 129-144 (2022).

23. Harry, W. "Structural determination of paraffin boiling points", Journal of the American Chemical Society, 69(1), pp. 17-20 (1947).

24. Gao, W., Iqbal, Z., Akhter, S., et al. "On irregularity descriptors of derived graphs", AIMS Mathematics, 5(5), pp. 4085-4107 (2020).

25. Das, S. and Rai, S. "M-polynomial and related degreebased topological indices of the third type of hexderived network", Nanosystems: Physics, Chemistry, Mathematics, 11(3), pp. 267-274 (2020).

26. Das, S. and Rai, S. "M-polynomial and related degreebased topological indices of the third type of chain hexderived network", Malaya Journal of Matematik, 8(4), pp. 1842-1850 (2020).

27. Iqbal, Z., Ishaq, M., Aslam, A., et al. "The measure of irregularities of nanosheets", Open Physics, 18(1), pp. 419-431 (2020).

28. Das, S. and Kumar, V. "On M-polynomial of the twodimensional Silicon-Carbons", Palestine Journal of Mathematics, 11(Special Issue II), pp. 136-157 (2022).

29. Albertson, M.O. "The irregularity of the graph", Ars Combinatoria, 46, pp. 219-225 (1997).

30. Dimitrov, D. and Reti, T. "Graphs with equal irregularity indices", Acta Polytechnica Hungarica, 11(4), pp. 41-57 (2014).

31. Das, S. and Mishra, U. "Calculation of various irregularity indices for stepwise irregular complete bipartite graph", in Proceedings of the Mathematical Society, Banaras Hindu University, 34, pp. 1-4 (2019).

32. Hammack, R.H., Imrich, W., and Klavzar, S., Handbook of Product Graphs, 2nd Edn., CRC Press, Boca Raton, FL, USA (2011).

33. Tavakoli, M., Rahbarnia, F., and Ashrafi, A.R., "Studying the corona product of graphs under some graph invariants", Transactions on Combinatorics, 3(3), pp. 43-49 (2014).

34. Maheswari, S.U. and Maheswari, B. "Some properties of cartesian product graphs of cayley graphs with arithmetic graphs", International Journal of Computer Applications, 138(3), pp. 26-29 (2012).

35. Pattabiraman, K. and Kandan, P. "Weighted PI index of corona product of graphs", Discrete Mathematics, Algorithms and Applications, 6(4), 1450055 (2014).

2. Abdo, H., Dimitrov, D., and Gutman, I. "Graphs with maximal irregularity", Discrete Applied Mathematics, 250, pp. 57-64 (2018).

3. Gao, W., Aamir, M., Iqbal, Z., et al. "On irregularity measures of some dendrimers structures", Mathematics, 7(3), p. 271 (2019).

4. Reti, T. "On some properties of graph irregularity indices with a particular regard to the -index", Applied Mathematics and Computation, 344, pp. 107- 115 (2019).

5. Gutman, I. "Stepwise irregular graphs", Applied Mathematics and Computation, 325, pp. 234-238 (2018).

6. Gutman, I. and Reti, T. "Note on irregular graphs", Bulletin (Academie serbe des sciences et des arts. Classe des sciences mathematiques et naturelles. Sciences mathematiques), 43, pp. 5-16 (2018).

7. Bell, F.K. "A note on the irregularity of graphs", Linear Algebra and Its Applications, 161, pp. 45-54 (1992).

8. Chartrand, G., Erdos, P., and Oellermann, O.R. "How to define an irregular graph", The College Mathematics Journal, 19(1), pp. 36-42 (1988).

9. Gutman, I., Hansen, P., andMelot, H. "Variable neighborhood search for extremal graphs. 10. comparison of irregularity indices for chemical trees", Journal of Chemical Information and Modeling, 45(2), pp. 222 -230 (2005).

10. Dobrynin, A.A. and Sharafdini, R. "Stepwise transmission irregular graphs", Applied Mathematics and Computation, 371, 124949 (2020).

11. Xu, K. and Klavzar, S. "Constructing new families of transmission irregular graphs", Discrete Applied Mathematics, 289, pp. 383-391 (2021).

12. Bezhaev, A.Y. and Dobrynin, A.A. "On quartic transmission irregular graphs", Applied Mathematics and Computation, 399, 126049 (2021).

13. Estrada, E. "Randic index, irregularity and complex biomolecular networks", Acta Chimica Slovenica, 57(3), pp. 597-603 (2010).

14. Balaban, A.T. "Applications of graph theory in chemistry", The Journal for Chemical Information and Computer Scientists, 25(3), pp. 334-343 (1985).

15. Garca-Domenech, R., Galvez, J., Julian-Ortiz, J.V., et al. "Some new trends in chemical graph theory", Chemical Reviews, 108(3), pp. 1127-1169 (2008).

16. Burch, K.J. "Chapter 8: Chemical applications of graph theory", in Mathematical Physics in Theoretical Chemistry (S. Blinder and J. House, eds.), Developments in Physical & Theoretical Chemistry, Elsevier, pp. 261-294 (2019).

17. Gutman, I. and Trinajstic, N. "Graph theory and molecular orbitals. Total '-electron energy of alternant hydrocarbons", Chemical Physics Letters, 17(4), pp. 535-538 (1972).

18. Das, S. and Rai, S. "Degree-based topological descriptors of type 3 rectangular hex-derived networks", Bulletin of the Institute of Combinatorics and its Applications, 95, pp. 21-37 (2022).

19. Dobrynin, A.A. and Kochetova, A.A. "Degree distance of a graph: A degree analog of the wiener index", Journal of Chemical Information and Computer Sciences, 34(5), pp. 1082-1086 (1994).

20. Khadikar, P.V. "On a novel structural descriptor PI", National Academy Science Letters, 23, pp. 113-118 (2000).

21. Das, S. and Rai, S. "Topological characterization of the third type of triangular hex-derived networks", Scientific Annals of Computer Science, 31(2), pp. 145- 161 (2021).

22. Das, S. and Kumar, V. "Investigation of closed derivation formulas for GQ and QG indices of a graph via M-polynomial", Iranian Journal of Mathematical Chemistry, 13(2), pp. 129-144 (2022).

23. Harry, W. "Structural determination of paraffin boiling points", Journal of the American Chemical Society, 69(1), pp. 17-20 (1947).

24. Gao, W., Iqbal, Z., Akhter, S., et al. "On irregularity descriptors of derived graphs", AIMS Mathematics, 5(5), pp. 4085-4107 (2020).

25. Das, S. and Rai, S. "M-polynomial and related degreebased topological indices of the third type of hexderived network", Nanosystems: Physics, Chemistry, Mathematics, 11(3), pp. 267-274 (2020).

26. Das, S. and Rai, S. "M-polynomial and related degreebased topological indices of the third type of chain hexderived network", Malaya Journal of Matematik, 8(4), pp. 1842-1850 (2020).

27. Iqbal, Z., Ishaq, M., Aslam, A., et al. "The measure of irregularities of nanosheets", Open Physics, 18(1), pp. 419-431 (2020).

28. Das, S. and Kumar, V. "On M-polynomial of the twodimensional Silicon-Carbons", Palestine Journal of Mathematics, 11(Special Issue II), pp. 136-157 (2022).

29. Albertson, M.O. "The irregularity of the graph", Ars Combinatoria, 46, pp. 219-225 (1997).

30. Dimitrov, D. and Reti, T. "Graphs with equal irregularity indices", Acta Polytechnica Hungarica, 11(4), pp. 41-57 (2014).

31. Das, S. and Mishra, U. "Calculation of various irregularity indices for stepwise irregular complete bipartite graph", in Proceedings of the Mathematical Society, Banaras Hindu University, 34, pp. 1-4 (2019).

32. Hammack, R.H., Imrich, W., and Klavzar, S., Handbook of Product Graphs, 2nd Edn., CRC Press, Boca Raton, FL, USA (2011).

33. Tavakoli, M., Rahbarnia, F., and Ashrafi, A.R., "Studying the corona product of graphs under some graph invariants", Transactions on Combinatorics, 3(3), pp. 43-49 (2014).

34. Maheswari, S.U. and Maheswari, B. "Some properties of cartesian product graphs of cayley graphs with arithmetic graphs", International Journal of Computer Applications, 138(3), pp. 26-29 (2012).

35. Pattabiraman, K. and Kandan, P. "Weighted PI index of corona product of graphs", Discrete Mathematics, Algorithms and Applications, 6(4), 1450055 (2014).

Transactions on Computer Science & Engineering and Electrical Engineering (D)

May and June 2023Pages 1049-1057