episciences.org_1259_1660008876 1660008876 episciences.org raphael.tournoy+crossrefapi@ccsd.cnrs.fr episciences.org Discrete Mathematics & Theoretical Computer Science 1365-8050 04 15 2014 Vol. 16 no. 1 Graph Theory On the Cartesian product of of an arbitrarily partitionable graph and a traceable graph Olivier Baudon Julien Bensmail Rafał Kalinowski Antoni Marczyk Jakub Przybyło Mariusz Wozniak Graph Theory A graph G of order n is called arbitrarily partitionable (AP, for short) if, for every sequence τ=(n1,\textellipsis,nk) of positive integers that sum up to n, there exists a partition (V1,\textellipsis,Vk) of the vertex set V(G) such that each set Vi induces a connected subgraph of order ni. A graph G is called AP+1 if, given a vertex u∈V(G) and an index q∈ &#x007b;1,\textellipsis,k&#x007d;, such a partition exists with u∈Vq. We consider the Cartesian product of AP graphs. We prove that if G is AP+1 and H is traceable, then the Cartesian product G□ H is AP+1. We also prove that G□H is AP, whenever G and H are AP and the order of one of them is not greater than four. 04 15 2014 1259 https://hal.archives-ouvertes.fr/hal-01179212v1 10.46298/dmtcs.1259 https://dmtcs.episciences.org/1259 https://dmtcs.episciences.org/1259/pdf