Weighted Edge-Decompositions of Graphs

Abstract

We prove tight estimates on the minimum weight of an edge decomposition of the complete graph into subgraphs of 3 or 4 edges, where the weight of a subgraph is the number of its vertices. We conjecture that the weighted edge decomposition problem on general graphs is NP-complete for every $k>2$. This conjecture is shown to be true for every $k\le 11$ except $k=8$. The problem is motivated by the traffic grooming problem for optical networks.