10.46298/dmtcs.1259
https://dmtcs.episciences.org/1259
Baudon, Olivier
Olivier
Baudon
Bensmail, Julien
Julien
Bensmail
Kalinowski, Rafał
Rafał
Kalinowski
Marczyk, Antoni
Antoni
Marczyk
Przybyło, Jakub
Jakub
Przybyło
Wozniak, Mariusz
Mariusz
Wozniak
On the Cartesian product of of an arbitrarily partitionable graph and a traceable graph
Graph Theory
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.
episciences.org
Discrete Mathematics
[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
2015-07-23
2014-04-15
2014-04-15
en
journal article
https://hal.archives-ouvertes.fr/hal-01179212v1
1365-8050
https://dmtcs.episciences.org/1259/pdf
VoR
application/pdf
Discrete Mathematics & Theoretical Computer Science
Vol. 16 no. 1
Graph Theory
Researchers
Students