On domination numbers of graphs bundles (Q854408)

The Cartesian product \(G\square H\) of two graphs \(G\) and \(H\) is the graph with vertex set \(V_G\times V_H\) and \((a,c)(b,d)\) is an edge of \(G\square H\) if \(c=d\) and \(ab\in E_G\), or \(a=b\) and \(cd\in E_H\). Given two graphs \(B\) and \(F\), a graph \(G\) is Cartesian graph bundle with fibre \(F\) over the base graph \(B\) if there is a graph map \(p:G\rightarrow B\) such that for each vertex \(v\in V_B\), \(p^{-1}(v)\simeq F\), and for each edge \(e\in E_B\), \(p^{-1}(e)\simeq K_2\square F\). The bundle \(G\) is obviously determined by \(F, B\) and a mapping \(\varphi:B_E\rightarrow\text{Aut}(F)\) which assigns an automorphism of the graph \(F\) to any edge of \(B\), and is written \(G=B\square_\varphi F\). The authors study the domination number of graph bundles, in particular of the Cartesian graph bundles over cycles. Here, the domination number \(\gamma(G)\) of \(G\) is the minimum cardinality of a set \(D\subseteq V_G\) such that every vertex outside \(D\) has a neighbor in \(D\). The authors show that for any integer \(k\geq 0\) there exists a graph \(G\) such that \(\gamma(G\square_\varphi C_4)=\gamma(G)\gamma(C_4)-2k\). This implies that the Vizing's conjecture (i.e., \(\gamma(G\square H)\geq\gamma(G)\gamma(H)\) for all graphs \(G\) and \(H\)) cannot be generalized to graph bundles. They also discuss the donination number of `strong' graph bundles.