The relaxed square property

zbMATH Open1321.05221arXiv1407.3164MaRDI QIDQ2947396FDOQ2947396

Authors: Marc Hellmuth, Tilen Marc, Lydia Ostermeier, Peter F. Stadler 

Publication date: 23 September 2015

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 K_23-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-relations can be obtained easily from finest RSP-relations on the prime factors.

Full work available at URL: https://arxiv.org/abs/1407.3164

Recommendations

• Unique square property, equitable partitions, and product-like graphs
• Unique square property and fundamental factorizations of graph bundles
• Factoring cartesian‐product graphs
• Algorithm for recognizing Cartesian graph bundles
• scientific article; zbMATH DE number 227249

zbMATH Keywords

RSP-relations

Mathematics Subject Classification ID

Graph operations (line graphs, products, etc.) (05C76)

Cited In (3)

• Unique square property, equitable partitions, and product-like graphs
• Unique square property and fundamental factorizations of graph bundles
• The Bishop-Phelps-Bollobás property and lush spaces

This page was built for publication: The relaxed square property

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2947396)