Subscribe to Syndicate

Marc Hellmuth

The three standard products (the Cartesian, the direct and the strong product) of undirected graphs have been repeatedly studied, unique prime factor decomposition (PFD) is known and polynomial time algorithms have been established for determining the prime factors. For directed graphs, unique PFD results with respect to the standard products are known. However, there is, until now, no known algorithm to compute the PFD of directed graphs with respect to the direct and the strong product in general.
Symbolic ultrametrics define edge-colored complete graphs Kn and yield a simple tree representation of Kn. We discuss, under which conditions this idea can be generalized to find a symbolic ultrametric that, in addition, distinguishes between edges and non-edges of arbitrary graphs G=(V,E) and thus, yielding a simple tree representation of G. We prove that such a symbolic ultrametric can only be defined for G if and only if G is a so-called cograph. A cograph is uniquely determined by a so-called cotree.
Graph products are characterized by the existence of non-trivial equivalence relations on the edge set of a graph that satisfy a so-called square property. We investigate here a generalization, termed RSP-relations . The class of graphs with non-trivial RSP-relations in particular includes graph bundles. Furthermore, RSP-relations are intimately related with covering graph constructions. For K 2, 3-free graphs finest RSP-relations can be computed in polynomial-time. In general, however, they are not unique and their number may even grow exponentially.

Pages