Algorithm for recognizing Cartesian graph bundles
Graph bundles generalize the notion of covering graphs and graph products. In [8], 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 [21], 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.
cartesian graph bundles unique square property fundamental factorization polynomial algorithm recognition