Opuscula Math. 43, no. 1 (2023), 81-100

Opuscula Mathematica

New results on imbalance graphic graphs

Sergiy Kozerenko
Andrii Serdiuk

Abstract. An edge imbalance provides a local measure of how irregular a given graph is. In this paper, we study graphs with graphic imbalance sequences. We give a new proof of imbalance graphicness for trees and use the new idea to prove that the same holds for unicyclic graphs. We then show that antiregular graphs are imbalance graphic and consider the join operation on graphs as well as the double graph operation. Our main results are concerning imbalance graphicness of three classes of block graphs: block graphs having all cut vertices in a single block; block graphs in which the subgraph induced by the cut vertices is either a star or a path. In the end, we discuss open questions and conjectures regarding imbalance graphic graphs.

Keywords: edge imbalance, irregularity of a graph, imbalance sequence, graphic sequence.

Mathematics Subject Classification: 05C07, 05C70, 05C99.

Full text (pdf)

  1. M.O. Albertson, The irregularity of a graph, Ars Comb. 46 (1997), 219-225.
  2. A. Ali, A survey of antiregular graphs, Contrib. Math. 1 (2020), 67-79. https://doi.org/10.47443/cm.2020.0021
  3. A. Ali, G. Chartrand, P. Zhang, Irregularity in Graphs, Springer, Cham, Switzerland, 2021.
  4. A.R. Ashrafi, A. Ghalavand, A. Ali, Molecular trees with the sixth, seventh and eighth minimal irregularity values, Discrete Math. Algorithms Appl. 11 (2019), no. 1, 1950002, 10 pp. https://doi.org/10.1142/S1793830919500010
  5. M. Behzad, G. Chartrand, No graph is perfect, Amer. Math. Monthly 74 (1967), 962-963. https://doi.org/10.2307/2315277
  6. G. Chartrand, P. Erdős, O.R. Oellermann, How to define an irregular graph, College Math. J. 19 (1988), no. 1, 36-42. https://doi.org/10.1080/07468342.1988.11973088
  7. P. Erdős, T. Gallai, Graphs with prescribed degrees of vertices, Mat. Lapok 11 (1960), 264-274.
  8. F. Goldberg, A spectral bound for graph irregularity, Czechoslovak Math. J. 65 (2015), no. 2, 375-379. https://doi.org/10.1007/s10587-015-0182-5
  9. I. Gutman, Stepwise irregular graphs, Appl. Math. Comput. 325 (2018), 234-238. https://doi.org/10.1016/j.amc.2017.12.045
  10. S. Kozerenko, Edge imbalance sequences and their graphicness, J. Adv. Math. Stud. 12 (2019), no. 1, 50-62.
  11. S. Kozerenko, V. Skochko, On graphs with graphic imbalance sequences, Algebra Discrete Math. 18 (2014), no. 1, 97-108.
  12. B.D. McKay, Various simple graphs: chordal graphs, https://users.cecs.anu.edu.au/~bdm/data/graphs.html.
  13. B.D. McKay, A. Piperno, nauty and Traces, Software distribution web pages: http://cs.anu.edu.au/~bdm/nauty/ and http://pallini.di.uniroma1.it/
  14. E. Munarini, C.P. Cippo, A. Scagliola, N. Salvi, Double graphs, Discrete Math. 308 (2008), no. 2-3, 242-254. https://doi.org/10.1016/j.disc.2006.11.038
  15. D. Rautenbach, I. Schiermeyer, Extremal problems for imbalanced edges, Graphs Combin. 22 (2006), no. 1, 103-111. https://doi.org/10.1007/s00373-005-0643-y
  16. D. Rautenbach, L. Volkmann, How local irregularity gets global in a graph, J. Graph Theory 41 (2002), no. 1, 18-23. https://doi.org/10.1002/jgt.10043
  17. A. Serdiuk, Imbalance graphic block graphs, 43rd Australiasian Combinatorics Conference, 13-17 December 2021, Melbourne, Australia.
  18. B. Zhou, W. Luo, On irregularity of graphs, Ars Comb. 88 (2008), 55-64.
  • Sergiy Kozerenko (corresponding author)
  • ORCID iD https://orcid.org/0000-0002-5716-3084
  • National University of Kyiv-Mohyla Academy, Faculty of Computer Sciences, Department of Mathematics, Skovorody Str. 2, 04070 Kyiv, Ukraine
  • Andrii Serdiuk
  • National University of Kyiv-Mohyla Academy, Faculty of Computer Sciences, Department of Mathematics, Skovorody Str. 2, 04070 Kyiv, Ukraine
  • Communicated by Mirko Horňák.
  • Received: 2022-08-23.
  • Accepted: 2022-11-25.
  • Published online: 2022-12-30.
Opuscula Mathematica - cover

Cite this article as:
Sergiy Kozerenko, Andrii Serdiuk, New results on imbalance graphic graphs, Opuscula Math. 43, no. 1 (2023), 81-100, https://doi.org/10.7494/OpMath.2023.43.1.81

Download this article's citation as:
a .bib file (BibTeX),
a .ris file (RefMan),
a .enw file (EndNote)
or export to RefWorks.

We advise you this website uses cookies to allow us to see how the site is used. All data is anonymized.
All recent versions of popular browsers give users a level of control over cookies. Users can set their browsers to accept or reject all, or certain, cookies.