Skip to Main content Skip to Navigation
Journal articles

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

Abstract : 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∈ {1,\textellipsis,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.
Document type :
Journal articles
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/hal-01179212
Contributor : Hélène Lowinger Connect in order to contact the contributor
Submitted on : Wednesday, July 22, 2015 - 9:14:55 AM
Last modification on : Saturday, June 25, 2022 - 10:35:48 AM
Long-term archiving on: : Friday, October 23, 2015 - 10:23:59 AM

File

dmtcs-16-1-14.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

Olivier Baudon, Julien Bensmail, Rafał Kalinowski, Antoni Marczyk, Jakub Przybyło, et al.. On the Cartesian product of of an arbitrarily partitionable graph and a traceable graph. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 1 (1), pp.225--232. ⟨10.46298/dmtcs.1259⟩. ⟨hal-01179212⟩

Share

Metrics

Record views

131

Files downloads

830