Recognizing Cartesian graph bundles

DOI10.1016/S0012-365X(96)00242-7MaRDI QIDQ1356477zbMATH OpenOpenAlexFDO

Authors Wilfried Imrich, Tomaž Pisanski, Janez Žerovnik

Publication date 25 November 1997

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(96)00242-7

zbMATH Keywords

Cartesian graph bundlegraph productsrecognition

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (05C99) Graph theory (including graph drawing) in computer science (68R10)

Review text

Graph bundles are extensions of covering graphs and graph products. The authors develop an algorithm that finds a representation as a nontrivial Cartesian graph bundle for all graphs that are Cartesian graph bundles over a triangle-free simple base. The problem of recognizing graph bundles over general base remains open.

Recommendations

• On recognizing Cartesian graph bundles
• Algorithm for recognizing Cartesian graph bundles
• Recognizing weighted directed cartesian graph bundles
• On recognition of strong graph bundles
• Recognizing triangulated Cartesian graph products
• Recognizing Berge graphs
• Recognizing Knödel graphs
• Recognizing graphs of acyclic cubical complexes
• Coloring graph bundles
• Recognizing decomposable graphs

Cites work

• A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
• Cartesian graph factorization at logarithmic cost per edge
• Coloring graph bundles
• Edge-colorability of graph bundles
• Factoring a graph in polynomial time
• Factoring cartesian‐product graphs
• Graph multiplication
• scientific article; zbMATH DE number 568809 (Why is no real title available?)
• Isomorphism Classes of Graph Bundles
• On Isometric Embeddings of Graphs
• Product graph representations
• The chromatic numbers of graph bundles over cycles

Cited in

(23)

• The edge fault-diameter of Cartesian graph bundles
• Algorithm for recognizing Cartesian graph bundles
• The chromatic numbers of graph bundles over cycles
• Time-dependent Lagrangian energy systems on supermanifolds with graph bundles
• Partial star products: a local covering approach for the recognition of approximate Cartesian product graphs
• The grid property and product-like hypergraphs
• On strong graph bundles
• Mixed fault diameter of Cartesian graph bundles
• Flow modules and nowhere-zero flows
• An algorithm forK-convex closure and an application
• On recognition of strong graph bundles
• Unique square property, equitable partitions, and product-like graphs
• Nowhere-zero flows in Cartesian bundles of graphs
• Coloring graph bundles
• Recognizing weighted directed cartesian graph bundles
• Improved upper bounds for vertex and edge fault diameters of Cartesian graph bundles
• A local prime factor decomposition algorithm
• On recognizing Cartesian graph bundles
• Graph bundles and Ricci‐flatness
• Recognizing graph products and bundles
• Recognizing triangulated Cartesian graph products
• On domination numbers of graphs bundles
• Distance-residual subgraphs

This page was built for publication: Recognizing Cartesian graph bundles

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