### 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 Woźniak*

#### Abstract

A graph G of order n is called arbitrarily
partitionable (AP, for short) if, for every sequence
τ=(n

_{1},…,n_{k}) of positive integers that sum up to n, there exists a partition (V_{1},…,V_{k}) of the vertex set V(G) such that each set V_{i}induces a connected subgraph of order n_{i}. A graph G is called AP+1 if, given a vertex u∈V(G) and an index q∈ {1,…,k}, such a partition exists with u∈V_{q}. 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.Full Text: PDF PostScript