We introduce the notion of m-bonacci-sum graphs denoted by Gm,n for positive integers m, n. The vertices of Gm,n are 1,2, …, n and any two vertices are adjacent if and only if their sum is an m-bonacci number. We show that Gm,n is bipartite and for (Formula presented) has exactly (m-1) components. We also find the values of n such that Gm,n contains cycles as subgraphs. We also use this graph to partition the set {1,2, …, n} into m-1 subsets such that each subset is ordered in such a way that sum of any 2 consecutive terms is an m-bonacci number. © Springer Nature Switzerland AG 2019.