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
τ=(n1,…,nk) of positive
integers that sum up to n, there exists a partition
(V1,…,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∈
{1,…,k}, 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.
Full Text: PDF PostScript