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/