Geodesic
More Aspects of Arbitrarily Partitionable Graphs
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 4, pp. 1237-1261.

Voir la notice de l'article provenant de la source Library of Science

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: arbitrarily partitionable graphs, partition into connected subgraphs, Hamiltonicity 
@article{DMGT_2022_42_4_a13,
     author = {Bensmail, Julien and Li, Binlong},
     title = {More {Aspects} of {Arbitrarily} {Partitionable} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1237--1261},
     publisher = {mathdoc},
     volume = {42},
     number = {4},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a13/}
}
TY  - JOUR
AU  - Bensmail, Julien
AU  - Li, Binlong
TI  - More Aspects of Arbitrarily Partitionable Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 1237
EP  - 1261
VL  - 42
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a13/
LA  - en
ID  - DMGT_2022_42_4_a13
ER  - 
%0 Journal Article
%A Bensmail, Julien
%A Li, Binlong
%T More Aspects of Arbitrarily Partitionable Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 1237-1261
%V 42
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a13/
%G en
%F DMGT_2022_42_4_a13
Bensmail, Julien; Li, Binlong. More Aspects of Arbitrarily Partitionable Graphs. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 4, pp. 1237-1261. http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a13/

[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

[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

[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

[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.689

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

[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

[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

[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

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

[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

[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

[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

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

[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

[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

[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).

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

[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

[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

[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

[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

[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

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

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