Decomposition of product graphs into paths and stars on five vertices

Abstract

Let Sk and Kk respectively denote a path, a star and a complete graph on k vertices. By a -decomposition of a graph G, we mean a decomposition of G into r copies of and s copies of In this paper, it shown that the graph admits a -decomposition if and only if where denotes a tensor product of complete graphs. Also we extend the existence of such a decomposition in complete m-partite graphs.

Keywords

• path
• star
• tensor product
• graph decomposition