1. bookVolume 42 (2022): Issue 4 (November 2022)
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

More Aspects of Arbitrarily Partitionable Graphs

Published Online: 12 Jul 2022
Volume & Issue: Volume 42 (2022) - Issue 4 (November 2022)
Page range: 1237 - 1261
Received: 09 Mar 2020
Accepted: 08 Jun 2020
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

A graph G of order n is arbitrarily partitionable (AP) if, for every sequence (n1, . . ., np) partitioning n, there is a partition (V1, . . ., ,Vp) of V (G) such that G[Vi] is a connected ni-graph for i = 1, . . ., p. The property of being AP is related to other well-known graph notions, such as perfect matchings and Hamiltonian cycles, with which it shares several properties. This work is dedicated to studying two aspects behind AP graphs.

On the one hand, we consider algorithmic aspects of AP graphs, which received some attention in previous works. We first establish the NP-hardness of the problem of partitioning a graph into connected subgraphs following a given sequence, for various new graph classes of interest. We then prove that the problem of deciding whether a graph is AP is in NP for several classes of graphs, confirming a conjecture of Barth and Fournier for these.

On the other hand, we consider the weakening to APness of su cient conditions for Hamiltonicity. While previous works have suggested that such conditions can sometimes indeed be weakened, we here point out cases where this is not true. This is done by considering conditions for Hamiltonicity involving squares of graphs, and claw- and net-free graphs.

Keywords

MSC 2010

[1] D. Barth, O. Baudon and J. Puech, Decomposable trees: a polynomial algorithm for tripodes, Discrete Appl. Math. 119 (2002) 205–216. https://doi.org/10.1016/S0166-218X(00)00322-X Search in Google Scholar

[2] D. Barth and H. Fournier, A degree bound on decomposable trees, Discrete Math. 306 (2006) 469–477. https://doi.org/10.1016/j.disc.2006.01.006 Search in Google Scholar

[3] O. Baudon, J. Bensmail, F. Foucaud and M. Pilśniak, Structural properties of recursively partitionable graphs with connectivity 2, Discuss. Math. Graph Theory 37 (2017) 89–115. https://doi.org/10.7151/dmgt.1925 Search in Google Scholar

[4] O. Baudon, F. Gilbert and M. Woźniak, Recursively arbitrarily vertex-decomposable graphs, Opuscula Math. 32 (2012) 689–706. https://doi.org//10.7494/OpMath.2012.32.4.68910.7494/OpMath.2012.32.4.689 Search in Google Scholar

[5] J. Bensmail, Partitions and decompositions of graphs, PhD. Thesis (Université de Bordeaux, France, 2014). Search in Google Scholar

[6] J. Bensmai, On the complexity of partitioning a graph into a few connected subgraphs, J. Comb. Optim. 30 (2015) 174–187. https://doi.org/10.1007/s10878-013-9642-8 Search in Google Scholar

[7] 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 Search in Google Scholar

[8] J.A. Bondy and V. Chvátal, A method in graph theory, Discrete Math. 15 (1976) 111–135. https://doi.org/10.1016/0012-365X(76)90078-9 Search in Google Scholar

[9] S. Brandt, Finding vertex decompositions in dense graphs (2013), personal communication. Search in Google Scholar

[10] H. Broersma, D. Kratsch and G.J. Woeginger, Fully decomposable split graphs, European J. Combin. 34 (2013) 567–575. https://doi.org/10.1016/j.ejc.2011.09.044 Search in Google Scholar

[11] M. Dell’Amico and S. Martello, Reduction of the three-partition problem, J. Comb. Optim. 3 (1999) 17–30. https://doi.org/10.1023/A:1009856820553 Search in Google Scholar

[12] M.E. Dyer and A.M. Frieze, On the complexity of partitioning graphs into connected subgraphs, Discrete Appl. Math. 10 (1985) 139–153. https://doi.org/10.1016/0166-218X(85)90008-3 Search in Google Scholar

[13] J. Edmonds, Paths, trees, and flowers, Canad. J. Math. 17 (1965) 449–467. https://doi.org/10.4153/CJM-1965-045-4 Search in Google Scholar

[14] R. Faudree, E. Flandrin and Z. Ryjáček, Claw-free graphs—A survey, Discrete Math. 164 (1997) 87–147. https://doi.org/10.1016/S0012-365X(96)00045-3 Search in Google Scholar

[15] H. Fleischner, In the square of graphs, Hamiltonicity and pancyclicity, Hamiltonian connectedness and panconnectedness are equivalent concepts, Monatsh. Math. 82 (1976) 125–149. https://doi.org/10.1007/BF01305995 Search in Google Scholar

[16] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (W.H. Freeman Co., New York, 1990). Search in Google Scholar

[17] E. Győri, On division of graphs to connected subgraphs, in: Combinatorics Proc. 5th Hungarian Colloq. (1976) 485–494. Search in Google Scholar

[18] M. Horňák, A. Marczyk, I. Schiermeyer and M. Woźniak, Dense arbitrarily vertex decomposable graphs, Graphs Combin. 28 (2012) 807–821. https://doi.org/10.1007/s00373-011-1077-3 Search in Google Scholar

[19] M. Horňák, Zs. Tuza and M. Woźniak, On-line arbitrarily vertex decomposable trees, Discrete Appl. Math. 155 (2007) 1420–1429. https://doi.org/10.1016/j.dam.2007.02.011 Search in Google Scholar

[20] R. Kalinowski, M. Pilśniak, I. Schiermeyer and M. Woźniak, Dense arbitrarily partitionable graphs, Discuss. Math. Graph Theory 36 (2016) 5–22. https://doi.org/10.7151/dmgt.1833 Search in Google Scholar

[21] L. Lovász, A homology theory for spanning trees of a graph, Acta Math. Acad. Sci. Hungar. 30 (1977) 241–251. https://doi.org/10.1007/BF01896190 Search in Google Scholar

[22] 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 Search in Google Scholar

[23] O. Ore, Note on Hamilton circuits, Amer. Math. Monthly 67 (1960) 55. https://doi.org/10.2307/2308928 Search in Google Scholar

[24] R. Ravaux, Graphes arbitrairement partitionnables: propriétés structurelles et algorithmiques, Ph.D. Thesis (Université de Versailles Saint-Quentin, France, 2009). Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo