On the Cartesian product of an arbitrarily partitionable graph and a traceable graph

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...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics and theoretical computer science 2014, Vol.16 (2), p.225-232
Main Authors: Baudon, Olivier, Bensmail, Julien, Kalinowski, Rafal, Marczyk, Antoni, Przybylo, Jakub, Woźniak, Mariusz
Format: Article
Language:English
Subjects:
Computer Science
Discrete Mathematics
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 GxH is AP+1. We also prove that GxH is AP, whenever G and H are AP and the order of one of them is not greater than four.
ISSN:1462-7264
1365-8050