Closure results for arbitrarily partitionable graphs

• Autorzy: Bensmail Julien

Identyfikatory

DOI

10.7494/OpMath.2024.44.6.773

• Języki publikacji: EN

Abstrakty

EN

A well-known result of Bondy and Chvátal establishes that a graph of order n is Hamiltonian if and only if its n-closure (obtained through repeatedly adding an edge joining any two non-adjacent vertices with degree sum at least n) also is. In this work, we investigate such closure results for arbitrarily partitionable graphs, a weakening of Hamiltonian graphs being those graphs that can be partitioned into arbitrarily many connected graphs of arbitrary orders. Among other results, we establish closure results for arbitrary partitions into connected graphs of order at most 3, for arbitrary partitions into connected graphs of order exactly any λ, and for the property of being arbitrarily partitionable in full.

Słowa kluczowe

EN

connected partition; arbitrarily partitionable graph; closure; traceability

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2024
• Tom: Vol. 44, no. 6
• Strony: 773--788
• Opis fizyczny: Bibliogr. 21 poz.

Twórcy

autor

Bensmail Julien

• Université Côte d’Azur, CNRS, Inria, I3S, France

• https://orcid.org/0000-0002-9292-394X

Bibliografia

• [1] D. Barth, O. Baudon, J. Puech, Decomposable trees: a polynomial algorithm for tripodes, Discrete Appl. Math. 119 (2002), no. 3, 205–216.
• [2] D. Barth, H. Fournier, A degree bound on decomposable trees, Discrete Math. 306 (2006), no. 5, 469–477.
• [3] J. Bensmail, On three polynomial kernels of sequences for arbitrarily partitionable graphs, Discrete Appl. Math. 202 (2016), 19–29.
• [4] J. Bensmail, Toughness properties of arbitrarily partitionable graphs, Université Côte d’Azur, 2023.
• [5] J. Bensmail, A σ3 condition for arbitrarily partitionable graphs, Discuss. Math. Graph Theory 44 (2024), no. 2, 755–776.
• [6] J. Bensmail, B. Li, More aspects of arbitrarily partitionable graphs, Discuss. Math. Graph Theory 42 (2022), no. 4, 1237–1261.
• [7] J.A. Bondy, V. Chvátal, A method in graph theory, Discrete Math. 15 (1976), no. 2, 111–135.
• [8] H. Broersma, D. Kratsch, G.J. Woeginger, Fully decomposable split graphs, European J. Combin. 34 (2013), no. 3, 567–575.
• [9] H. Broersma, Z. Ryjáček, I. Schiermeyer, Closure concepts: a survey, Graphs Combin. 16 (2000), 17–48.
• [10] C. Buchanan, B. Du Preez, K.E. Perry, P. Rombach, Toughness of recursively partitionable graphs, Theory Appl. Graphs 10 (2023), no. 2, Article 4.
• [11] G.A. Dirac, Some theorems on abstract graphs, Proc. Lond. Math. Soc. (3) 2 (1952), 69–81.
• [12] M. Horňák, A. Marczyk, I. Schiermeyer, M. Woźniak, Dense arbitrarily vertex decomposable graphs, Graphs Combin. 28 (2012), 807–821.
• [13] M. Horňák, M. Woźniak, On arbitrarily vertex decomposable trees, Discrete Math. 308 (2008), no. 7, 1268–1281.
• [14] R. Kalinowski, M. Pilśniak, I. Schiermeyer, M. Woźniak, Dense arbitrarily partitionable graphs, Discuss. Math. Graph Theory 36 (2016), 5–22.
• [15] F. Liu, B. Wu, J. Meng, Arbitrarily partitionable {2K2,C4}-free graphs, Discuss. Math. Graph Theory 42 (2022), 485–500.
• [16] A. Marczyk, A note on arbitrarily vertex decomposable graphs, Opuscula Math. 26 (2006), no. 1, 109–118.
• [17] A. Marczyk, An Ore-type condition for arbitrarily vertex decomposable graphs, Discrete Math. 309 (2009), 3588–3594.
• [18] O. Ore, Note on Hamilton circuits, Amer. Math. Monthly 67 (1960), 55.
• [19] M.D. Plummer, A. Saito, Closure and factor-critical graphs, Discrete Math. 215 (2000), 171–179.
• [20] R. Ravaux, Decomposing trees with large diameter, Theor. Comput. Sci. 411 (2010), 3068–3072.
• [21] W.T. Tutte, The factorization of locally finite graphs, Canad. J. Math. 2 (1950), 44–49.

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)