Couterexample to a conjecture on the structure of bipartite partionable graphs
Richard G. Gibson, Christina M. Mynhardt · Discussiones Mathematicae Graph Theory · 2007
A graph G is called a prism fixer if (G ×K2) = (G), where (G) denotes the domination number of G. A symmetric -set of G is a minimum dominating set D which admits a partition D = D1 ∪ D2 such that V (G) − N[Di] = Dj, i,j = 1,2, i 6 j. It is known that G is a prism fixer if and only if G has a symmetric -set. Hartnell and Rall [On dominating the Cartesian product of a graph and K2, Discuss. Math. Graph Theory 24 (2004), 389–402] conjectured that if G is a connected, bipartite graph such that V (G) can be partitioned into symmetric -sets, then G ∼ C4 or G can be obtained from K2t,2t by removing the edges of t vertex-disjoint 4-cycles. We construct a counterexample to this conjecture and prove an alternative result on the structure of such bipartite graphs.