Fraunhofer-Gesellschaft

Publica

Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

The relaxed square property

 
: Hellmuth, M.; Marc, T.; Ostermeier, L.; Stadler, P.F.

Australasian Journal of Combinatorics 62 (2015), No.3, pp.240-270
ISSN: 1034-4942
English
Journal Article
Fraunhofer IZI ()

Abstract
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 K2,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. They behave well for graph products, however, in sense that a finest RSP-relation can be obtained easily from finest RSP-relations on the prime factors.

: http://publica.fraunhofer.de/documents/N-418222.html