2015/01/16 by Marc Hellmuth, Hellmuth, Marc, Nicolas Wieseke +1
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Graph Labeling and Dimension Problems #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.1501.03931
openalex publication_date 2015/01/16 · openalex created_date 2022/10/05 · openalex updated_date 2026/07/28
Symbolic ultrametrics define edge-colored complete graphs Kn and yield a\nsimple tree representation of Kn. We discuss, under which conditions this idea\ncan be generalized to find a symbolic ultrametric that, in addition,\ndistinguishes between edges and non-edges of arbitrary graphs G=(V,E) and thus,\nyielding a simple tree representation of G. We prove that such a symbolic\nultrametric can only be defined for G if and only if G is a so-called cograph.\nA cograph is uniquely determined by a so-called cotree. As not all graphs are\ncographs, we ask, furthermore, what is the minimum number of cotrees needed to\nrepresent the topology of G. The latter problem is equivalent to find an\noptimal cograph edge k-decomposition E1,...,Ek of E so that each subgraph\n(V,Ei) of G is a cograph. An upper bound for the integer k is derived and it\nis shown that determining whether a graph has a cograph 2-decomposition, resp.,\n2-partition is NP-complete.\n