{"docId":1259,"paperId":1259,"url":"https:\/\/dmtcs.episciences.org\/1259","doi":"10.46298\/dmtcs.1259","journalName":"Discrete Mathematics & Theoretical Computer Science","issn":"","eissn":"1365-8050","volume":[{"vid":101,"name":"Vol. 16 no. 1"}],"section":[{"sid":9,"title":"Graph Theory","description":[]}],"repositoryName":"Hal","repositoryIdentifier":"hal-01179212","repositoryVersion":1,"repositoryLink":"https:\/\/hal.archives-ouvertes.fr\/hal-01179212v1","dateSubmitted":"2012-11-23 00:00:00","dateAccepted":"2015-07-23 10:50:51","datePublished":"2014-04-15 00:00:00","titles":{"en":"On the Cartesian product of of an arbitrarily partitionable graph and a traceable graph"},"authors":["Baudon, Olivier","Bensmail, Julien","Kalinowski, Rafa\u0142","Marczyk, Antoni","Przyby\u0142o, Jakub","Wozniak, Mariusz"],"abstracts":{"0":"Graph Theory","en":"A graph G of order n is called arbitrarily partitionable (AP, for short) if, for every sequence \u03c4=(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\u2208V(G) and an index q\u2208 {1,\\textellipsis,k}, such a partition exists with u\u2208Vq. 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\u25a1 H is AP+1. We also prove that G\u25a1H is AP, whenever G and H are AP and the order of one of them is not greater than four."},"keywords":[{"en":"Discrete Mathematics"},"[INFO.INFO-DM] Computer Science [cs]\/Discrete Mathematics [cs.DM]"]}