Georgia Institute of Technology College of Sciences

We study the minimum number of paths needed to express the edge set of a given graph as the symmetric difference of the edge sets of the paths. This can be seen as a weakening of Gallai’s path decomposition problem, and a variant of the “odd cover” problem of Babai and Frankl which asks for the minimum number of complete bipartite graphs whose symmetric difference gives the complete graph. We relate this “path odd-cover” number of a graph to other known graph parameters and prove some bounds. Joint work with Steffen Borgwardt, Calum Buchanan, Eric Culver, Bryce Frederickson, and Puck Rombach.