Opuscula Math. 43, no. 1 (2023), 81-100
https://doi.org/10.7494/OpMath.2023.43.1.81
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.
- M.O. Albertson, The irregularity of a graph, Ars Comb. 46 (1997), 219-225.
- A. Ali, A survey of antiregular graphs, Contrib. Math. 1 (2020), 67-79. https://doi.org/10.47443/cm.2020.0021
- A. Ali, G. Chartrand, P. Zhang, Irregularity in Graphs, Springer, Cham, Switzerland, 2021.
- 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
- M. Behzad, G. Chartrand, No graph is perfect, Amer. Math. Monthly 74 (1967), 962-963. https://doi.org/10.2307/2315277
- 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
- P. Erdős, T. Gallai, Graphs with prescribed degrees of vertices, Mat. Lapok 11 (1960), 264-274.
- 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
- I. Gutman, Stepwise irregular graphs, Appl. Math. Comput. 325 (2018), 234-238. https://doi.org/10.1016/j.amc.2017.12.045
- S. Kozerenko, Edge imbalance sequences and their graphicness, J. Adv. Math. Stud. 12 (2019), no. 1, 50-62.
- S. Kozerenko, V. Skochko, On graphs with graphic imbalance sequences, Algebra Discrete Math. 18 (2014), no. 1, 97-108.
- B.D. McKay, Various simple graphs: chordal graphs, https://users.cecs.anu.edu.au/~bdm/data/graphs.html.
- 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/
- 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
- 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
- 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
- A. Serdiuk, Imbalance graphic block graphs, 43rd Australiasian Combinatorics Conference, 13-17 December 2021, Melbourne, Australia.
- B. Zhou, W. Luo, On irregularity of graphs, Ars Comb. 88 (2008), 55-64.
- Sergiy Kozerenko (corresponding author)
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.
