The relaxed square property

MaRDI QIDQ2947396zbMATH OpenFDO

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

Publication date 23 September 2015

Full work available at URL https://arxiv.org/abs/1407.3164, http://ajc.maths.uq.edu.au//pdf/62/ajc_v62_p240.pdf

zbMATH Keywords

RSP-relations

Mathematics Subject Classification ID

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

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.

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

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)