Some properties of stepwise irregular graphs

Somnath Bera, Prithwineel Paul, K.G. Subramanian

Abstract


Graphs in which the absolute difference between the degrees of any two adjacent vertices is exactly one, are called stepwise irregular (SI) graphs. We establish several properties of SI graphs. In particular, we show that SI graphs of different order and cyclomatic numbers can be constructed from an SI graph with a vertex of degree 1 or 2. Necessary conditions and sufficient conditions for a degree sequence to be SI graphic are obtained. Moreover, a necessary condition comparing the sum of the terms of a partition of SI graph and its conjugate partition is obtained. Properties of SI graphs under certain elementary graph operations are also investigated.


Keywords


graph irregularity; stepwise irregular graph; Albertson index; partition

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2026.14.1.14

References

H. Abdo, N. Cohen, and D. Dimitrov, "Graphs with maximal irregularity," FILOMAT, vol. 28, no. 7, pp. 1315–1322, 2014.

Y. Alavi and J. Liu, "Highly irregular digraphs," Discrete Mathematics, vol. 111, pp. 3–10, 1993.

M. O. Albertson, "The irregularity of a graph," Ars Combinatoria, vol. 46, pp. 219–225, 1997.

G. E. Andrews and K. Eriksson, Integer Partitions, Cambridge University Press, 2004.

R. Criado, J. Flores, A. G. del Amo, and M. Romance, "Centralities of a network and its line graph: an analytical comparison by means of their irregularity," International Journal of Computer Mathematics, vol. 91, no. 2, pp. 304–314, 2014.

K. C. Das and I. Gutman, "Some properties of the Second Zagreb index," MATCH Communications in Mathematical and in Computer Chemistry, vol. 52, pp. 103–112, 2004.

T. Doslic, B. Furtula, A. Graovac, I. Gutman, S. Moradid, and Z. Yarahmadie, "On vertex degree based molecular structure descriptors," MATCH Communications in Mathematical and in Computer Chemistry, vol. 66, pp. 613–626, 2011.

C. Elphick and P. Wocjan, "New measures of graph irregularity," Electronic Journal of Graph Theory and Applications, vol. 2, pp. 52–65, 2014.

E. Estrada, "Randic index, irregularity and complex biomolecular networks," Acta Chimica Slovenica, vol. 57, pp. 597–603, 2010.

G. H. Fath-Tabar, "Old and new Zagreb indices of graphs," MATCH Communications in Mathematical and in Computer Chemistry, vol. 65, pp. 79–84, 2011.

I. Gutman, "Stepwise irregular graphs," Applied Mathematics and Computation, vol. 325, pp. 234–238, 2018.

I. Gutman and K. C. Das, "The first Zagreb index 30 years after," MATCH Communications in Mathematical and in Computer Chemistry, vol. 50, pp. 83–92, 2004.

I. Gutman, P. Hansen, and H. Melot, "Variable neighborhood search for extremal graphs 10. comparison of irregularity indices for chemical trees," Journal of Chemical Information and Modeling, vol. 45, no. 2, pp. 222–230, 2005.

F. Harary, Graph Theory, Addison-Wesley, Reading, MA, 1969.

M. A. Henning and D. Rautenbach, "On the irregularity of bipartite graphs," Discrete Mathematics, vol. 307, pp. 1467–1472, 2007.

S. Kitaev and V. Lozin, Words and Graphs, Monographs in Theoretical Computer Science. An EATCS Series, Springer Cham, 2016.

Z. Majcher and J. Michael, "Degree sequences of highly irregular graphs," Discrete Mathematics, vol. 164, pp. 225–236, 1997.

R. Merris, "Degree maximal graphs are laplacial integral," Linear Algebra and its Applications, vol. 199, pp. 381–389, 1994.

I. Wilfried and K. Sandi, Product graphs: structure and recognition, Wiley, 2000.


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats