Department of
Applied
Mathematics

Three Ways to Cover a Graph

Torsten Ueckerdt

Abstract

We are interested in covering the edges of a host graph H, e.g., the Petersen graph, with one or more graphs from a fixed template class, e.g., cycles. Edges of H may be covered more than once, but (of course) no non-edge shall be covered. Moreover, we want such a cover that is as sparse as possible. For instance we may want to use only few template graphs.

In this talk we discuss three different concepts of graph covers and sparsity, their similarities and differences.