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

DOI10.1016/J.DISC.2013.12.012zbMATH Open1281.05115DBLPjournals/dm/HellmuthOS14arXiv1301.6898OpenAlexW1578938677WikidataQ56267385 ScholiaQ56267385MaRDI QIDQ394372FDOQ394372

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

Publication date: 27 January 2014

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

equitable partitioncartesian graph productquotient graphsquare propertyunique square propertyUSP-relation

Mathematics Subject Classification ID

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

Cites Work

• Handbook of product graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Factoring cartesian‐product graphs
• Graph multiplication
• PERFECT STATE TRANSFER, GRAPH PRODUCTS AND EQUITABLE PARTITIONS
• Edge-colorability of graph bundles
• Title not available (Why is that?)
• Feasibility conditions for the existence of walk-regular graphs
• A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
• Product graph representations
• Approximate graph products
• Unique square property and fundamental factorizations of graph bundles
• Recognizing Cartesian graph bundles
• Algorithm for recognizing Cartesian graph bundles
• Partial star products: a local covering approach for the recognition of approximate Cartesian product graphs
• Locally constrained graph homomorphisms and equitable partitions
• An algorithm forK-convex closure and an application
• Isometric embeddings of graphs
• Title not available (Why is that?)
• A local prime factor decomposition algorithm
• Local algorithms for the prime factorization of strong product graphs
• Equitable partitions to spanning trees in a graph

Cited In (2)

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

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)