On recognizing Cartesian graph bundles

DOI10.1016/S0012-365X(00)00254-5MaRDI QIDQ5936045zbMATH OpenFDO

Authors Blaž Zmazek, Janez Žerovnik

Publication date 30 June 2002

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0012-365X(00)00254-5

zbMATH Keywords

Cartesian graph bundlepolynomial algorithmrecognition

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Review text

Let \(B\) and \(F\) be graphs. A graph \(G\) is a Cartesian graph bundle with fibre \(F\) over the base graph \(B\) if there is a mapping \(p:G\to B\) which satisfies the following conditions: (1) \(p\) maps adjacent vertices of \(G\) to adjacent or identical vertices of \(B\). (2) \(p\) maps edges to edges or vertices. (3) For each \(v\in V(B)\), \(p^-(v)\cong F\), and for every \(e\in E(B)\), \(p^{-1}(e)\) is the Cartesian product of \(K_2\) and \(F\).NEWLINENEWLINENEWLINEThe authors extend a polynomial algorithm for recognition of Cartesian graph bundles over \(K_3\)-free simple base to one for recognition of Cartesian graph bundles over a \(K_4\setminus e\) simple base, without induced \(K_{3,3}\).

Recommendations

• Algorithm for recognizing Cartesian graph bundles
• Recognizing weighted directed cartesian graph bundles
• Recognizing Cartesian graph bundles
• On recognition of strong graph bundles
• Unique square property and fundamental factorizations of graph bundles

Cited in

(14)

• The edge fault-diameter of Cartesian graph bundles
• Unique square property and fundamental factorizations of graph bundles
• Recognizing Cartesian graph bundles
• Algorithm for recognizing Cartesian graph bundles
• On strong graph bundles
• Mixed fault diameter of Cartesian graph bundles
• An algorithm forK-convex closure and an application
• On recognition of strong graph bundles
• Recognizing weighted directed cartesian graph bundles
• Improved upper bounds for vertex and edge fault diameters of Cartesian graph bundles
• ON THE HARDNESS OF RECOGNIZING BUNDLES IN TIME TABLE GRAPHS
• Robust Factorizations and Colorings of Tensor Graphs
• Recognizing graph products and bundles
• On domination numbers of graphs bundles

This page was built for publication: On recognizing Cartesian graph bundles

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