Opuscula Math. 44, no. 6 (2024), 773-788
https://doi.org/10.7494/OpMath.2024.44.6.773
Opuscula Mathematica
Closure results for arbitrarily partitionable graphs
Abstract. 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 \(\lambda\), and for the property of being arbitrarily partitionable in full.
Keywords: connected partition, arbitrarily partitionable graph, closure, traceability.
Mathematics Subject Classification: 05C99, 68R10.
- D. Barth, O. Baudon, J. Puech, Decomposable trees: a polynomial algorithm for tripodes, Discrete Appl. Math. 119 (2002), no. 3, 205-216. https://doi.org/10.1016/s0166-218x(00)00322-x
- D. Barth, H. Fournier, A degree bound on decomposable trees, Discrete Math. 306 (2006), no. 5, 469-477. https://doi.org/10.1016/j.disc.2006.01.006
- J. Bensmail, On three polynomial kernels of sequences for arbitrarily partitionable graphs, Discrete Appl. Math. 202 (2016), 19-29. https://doi.org/10.1016/j.dam.2015.08.016
- J. Bensmail, Toughness properties of arbitrarily partitionable graphs, Université Côte d'Azur, 2023.
- J. Bensmail, A \(\sigma_3\) condition for arbitrarily partitionable graphs, Discuss. Math. Graph Theory 44 (2024), no. 2, 755-776. https://doi.org/10.7151/dmgt.2471
- J. Bensmail, B. Li, More aspects of arbitrarily partitionable graphs, Discuss. Math. Graph Theory 42 (2022), no. 4, 1237-1261. https://doi.org/10.7151/dmgt.2343
- J.A. Bondy, V. Chvátal, A method in graph theory, Discrete Math. 15 (1976), no. 2, 111-135. https://doi.org/10.1016/0012-365x(76)90078-9
- H. Broersma, D. Kratsch, G.J. Woeginger, Fully decomposable split graphs, European J. Combin. 34 (2013), no. 3, 567-575. https://doi.org/10.1016/j.ejc.2011.09.044
- H. Broersma, Z. Ryjáček, I. Schiermeyer, Closure concepts: a survey, Graphs Combin. 16 (2000), 17-48. https://doi.org/10.1007/s003730050002
- C. Buchanan, B. Du Preez, K.E. Perry, P. Rombach, Toughness of recursively partitionable graphs, Theory Appl. Graphs 10 (2023), no. 2, Article 4. https://doi.org/10.20429/tag.2023.10204
- G.A. Dirac, Some theorems on abstract graphs, Proc. Lond. Math. Soc. (3) 2 (1952), 69-81. https://doi.org/10.1112/plms/s3-2.1.69
- M. Horňák, A. Marczyk, I. Schiermeyer, M. Woźniak, Dense arbitrarily vertex decomposable graphs, Graphs Combin. 28 (2012), 807-821. https://doi.org/10.1007/s00373-011-1077-3
- M. Horňák, M. Woźniak, On arbitrarily vertex decomposable trees, Discrete Math. 308 (2008), no. 7, 1268-1281. https://doi.org/10.1016/j.disc.2007.04.008
- R. Kalinowski, M. Pilśniak, I. Schiermeyer, M. Woźniak, Dense arbitrarily partitionable graphs, Discuss. Math. Graph Theory 36 (2016), 5-22. https://doi.org/10.7151/dmgt.1833
- F. Liu, B. Wu, J. Meng, Arbitrarily partitionable \(\{2K_2,C_4\}\)-free graphs, Discuss. Math. Graph Theory 42 (2022), 485-500. https://doi.org/10.7151/dmgt.2289
- A. Marczyk, A note on arbitrarily vertex decomposable graphs, Opuscula Math. 26 (2006), no. 1, 109-118.
- A. Marczyk, An Ore-type condition for arbitrarily vertex decomposable graphs, Discrete Math. 309 (2009), 3588-3594. https://doi.org/10.1016/j.disc.2007.12.066
- O. Ore, Note on Hamilton circuits, Amer. Math. Monthly 67 (1960), 55. https://doi.org/10.2307/2308928
- M.D. Plummer, A. Saito, Closure and factor-critical graphs, Discrete Math. 215 (2000), 171-179. https://doi.org/10.1016/s0012-365x(99)00234-4
- R. Ravaux, Decomposing trees with large diameter, Theor. Comput. Sci. 411 (2010), 3068-3072. https://doi.org/10.1016/j.tcs.2010.04.032
- W.T. Tutte, The factorization of locally finite graphs, Canad. J. Math. 2 (1950), 44-49. https://doi.org/10.4153/cjm-1950-005-2
- Julien Bensmail
https://orcid.org/0000-0002-9292-394X- Université Côte d'Azur, CNRS, Inria, I3S, France
- Communicated by Ingo Schiermeyer.
- Received: 2024-03-26.
- Revised: 2024-07-29.
- Accepted: 2024-09-09.
- Published online: 2024-10-11.
