Discrete Mathematics & Theoretical Computer Science, Vol 16, No 1 (2014)

Font Size:  Small  Medium  Large

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


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