Algorithm for recognizing Cartesian graph bundles Original Research Article

Graph bundles generalize the notion of covering graphs and graph products. In , authors constructed an algorithm that finds a presentation as a nontrivial Cartesian graph bundle for all graphs that are Cartesian graph bundles over triangle-free simple base. In , the unique square property is defined and it is shown that any equivalence relation possessing the unique square property determines the fundamental factorization of a graph as a nontrivial Cartesian graph bundle over arbitrary base graph. In this paper we define a relation Δ having a unique square property on Cartesian graph bundles over K4⧹e-free simple base. We also give a polynomial algorithm for recognizing Cartesian graph bundles over K4⧹e-free simple base.