Unique square property and fundamental factorizations of graph bundles (Q1349120)

Let \(B\) and \(F\) be graphs. Then a graph \(G\) is said to be a Cartesian graph bundle with fibre \(F\) over the base \(B\) if there is a map \(p:G\rightarrow B\) satisfying the conditions: (1) adjacent vertices of \(G\) are mapped to adjacent or identical vertices of \(B\); (2) the edges are mapped to edges or collapsed to a vertex; (3) for each vertex \(v\in V(B),p^{-1}(v)\cong F\) and for each edge \(e\in E(B), p^{-1}(e)\cong K_2 \square F\), the Cartesian product of \(K_2\) and \(F\). An edge \(e\) is degenerate if \(p(e)\) is a vertex and non-degenerate otherwise. In this paper the authors define an equivalence relation \(R\) on the edge set of a graph to have the unique square property if and only if any pair of adjacent edges which belong to distinct \(R\)-equivalence classes span exactly one square with opposite edges in the same \(R\)-equivalence class. A connected subgraph \(H\) of a graph \(G\) is said to be \(k\)-convex in \(G\), if for any pair of vertices \(u,v\) of \(H\) at distance at most \(k\), the set of all shortest \(u\)-\(v\) paths of \(G\) are contained in \(H\). A disconnected subgraph is \(k\)-convex if each component of it is \(k\)-convex. An equivalence relation \(R\) on \(E(G)\) is weakly \(k\)-convex if at least one equivalence class of \(R\) is \(k\)-convex. The equivalence relation \((D,N)\) where \(D\) is the set of degenerate edges and \(N\) is the set of non-degenerate edges of a presentation of a graph \(G\) as a Cartesian graph bundle is called the fundamental factorization of \(G\). The authors show that any weakly \(2\)-convex equivalence relation possessing the unique square property determines the fundamental factorization of a graph as a non-trivial Cartesian graph bundle over an arbitrary base graph, whenever it separates degenerate and non-degenerate edges of the factorization. They also provide an algorithm which finds at least one such presentation. This generalizes an earlier result with the base graph triangle-free.