ISBN 9783843942942

978-3-8439-4294-2, Reihe Mathematik

Irene Heinrich
On Graph Decomposition: Hajós' Conjecture, the Clustering Coefficient and Dominating Sets

179 Seiten, Dissertation Technische Universität Kaiserslautern (2019), Hardcover, A5

Zusammenfassung / Abstract

The heart of this thesis is a proof of Hajós' Conjecture for graphs of pathwidth at most 6.

We modify the techniques of the before mentioned proof in order to tackle two other conjectures restricted to graphs of small treewidth: Sabidussi's Compatibility Conjecture and the Three-Decomposition-Conjecture. Furthermore, we give equivalent characterizations of the class of graphs with the property that all cycle decompositions have the same cardinality.

We determine the maximum clustering coefficient among all connected regular graphs of a given order, as well as among all connected subcubic graphs of a given order; we characterize all extremal graphs in both cases, and, we determine the maximum increase of the clustering coefficient caused by adding a single edge.

Finally, we present a new representation of the domination polynomial as a sum over complete bipartite subgraphs. Moreover, we give a 5-approximation algorithm for a vertex subset that simultaneous dominates all cycles contained in a given graph.