Unique square property, equitable partitions, and product-like graphs

DOI10.1016/J.DISC.2013.12.012MaRDI QIDQ394372zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Marc Hellmuth, Lydia Ostermeier, Peter F. Stadler

Publication date 27 January 2014

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

cartesian graph productequitable partitionquotient graphsquare propertyunique square propertyUSP-relation

Mathematics Subject Classification ID

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

Abstract: Equivalence relations on the edge set of a graph $G$ that satisfy restrictive conditions on chordless squares play a crucial role in the theory of Cartesian graph products and graph bundles. We show here that such relations in a natural way induce equitable partitions on the vertex set of $G$, which in turn give rise to quotient graphs that can have a rich product structure even if $G$ itself is prime.

Recommendations

• The grid property and product-like hypergraphs
• Unique square property and fundamental factorizations of graph bundles
• Algorithm for recognizing Cartesian graph bundles
• The relaxed square property
• Factoring cartesian‐product graphs

Cites work

• A local prime factor decomposition algorithm
• A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
• Algorithm for recognizing Cartesian graph bundles
• An algorithm forK-convex closure and an application
• Approximate graph products
• Edge-colorability of graph bundles
• Equitable partitions to spanning trees in a graph
• Factoring cartesian‐product graphs
• Feasibility conditions for the existence of walk-regular graphs
• Graph multiplication
• Handbook of product graphs
• scientific article; zbMATH DE number 91031 (Why is no real title available?)
• scientific article; zbMATH DE number 3482387 (Why is no real title available?)
• scientific article; zbMATH DE number 496152 (Why is no real title available?)
• Isometric embeddings of graphs
• Local algorithms for the prime factorization of strong product graphs
• Locally constrained graph homomorphisms and equitable partitions
• Partial star products: a local covering approach for the recognition of approximate Cartesian product graphs
• Perfect state transfer on quotient graphs
• Perfect state transfer, graph products and equitable partitions
• Product graph representations
• Recognizing Cartesian graph bundles
• Unique square property and fundamental factorizations of graph bundles

Cited in

(3)

• Partial star products: a local covering approach for the recognition of approximate Cartesian product graphs
• The grid property and product-like hypergraphs
• The relaxed square property

This page was built for publication: Unique square property, equitable partitions, and product-like graphs

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