New results on imbalance graphic graphs

• Autorzy: Kozerenko Sergiy , Serdiuk Andrii

Identyfikatory

DOI

10.7494/OpMath.2023.43.1.81

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

edge imbalance; irregularity of a graph; imbalance sequence; graphic sequence

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2023
• Tom: Vol. 43, no. 1
• Strony: 81--100
• Opis fizyczny: Bibliogr. 18 poz., tab., wykr.

Twórcy

autor

Kozerenko Sergiy

• National University of Kyiv-Mohyla Academy, Faculty of Computer Sciences, Department of Mathematics, Skovorody Str. 2, 04070 Kyiv, Ukraine

• https://orcid.org/0000-0002-5716-3084

autor

Serdiuk Andrii

• National University of Kyiv-Mohyla Academy, Faculty of Computer Sciences, Department of Mathematics, Skovorody Str. 2, 04070 Kyiv, Ukraine

Bibliografia

• [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.
• [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.
• [5] M. Behzad, G. Chartrand, No graph is perfect, Amer. Math. Monthly 74 (1967), 962–963.
• [6] G. Chartrand, P. Erdős, O.R. Oellermann, How to define an irregular graph, College Math. J. 19 (1988), no. 1, 36–42.
• [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.
• [9] I. Gutman, Stepwise irregular graphs, Appl. Math. Comput. 325 (2018), 234–238.
• [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, nautyTraces, 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.
• [15] D. Rautenbach, I. Schiermeyer, Extremal problems for imbalanced edges, Graphs Combin. 22 (2006), no. 1, 103–111.
• [16] D. Rautenbach, L. Volkmann, How local irregularity gets global in a graph, J. Graph Theory 41 (2002), no. 1, 18–23.
• [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.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023)