Counterexample to a conjecture on the structure of bipartite partitionable graphs

Richard G. Gibson, and Christina M. Mynhardt. "Counterexample to a conjecture on the structure of bipartite partitionable graphs." Discussiones Mathematicae Graph Theory 27.3 (2007): 527-540. <http://eudml.org/doc/270301>.

@article{RichardG2007,
abstract = {A graph G is called a prism fixer if γ(G×K₂) = γ(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 = D₁∪ D₂ such that $V(G)-N[D_i] = D_j$, i,j = 1,2, i ≠ 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 K₂, 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 ≅ C₄ or G can be obtained from $K_\{2t,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.},
author = {Richard G. Gibson, Christina M. Mynhardt},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {domination; prism fixer; symmetric dominating set; bipartite graph},
language = {eng},
number = {3},
pages = {527-540},
title = {Counterexample to a conjecture on the structure of bipartite partitionable graphs},
url = {http://eudml.org/doc/270301},
volume = {27},
year = {2007},
}

TY - JOUR
AU - Richard G. Gibson
AU - Christina M. Mynhardt
TI - Counterexample to a conjecture on the structure of bipartite partitionable graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2007
VL - 27
IS - 3
SP - 527
EP - 540
AB - A graph G is called a prism fixer if γ(G×K₂) = γ(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 = D₁∪ D₂ such that $V(G)-N[D_i] = D_j$, i,j = 1,2, i ≠ 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 K₂, 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 ≅ C₄ or G can be obtained from $K_{2t,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.
LA - eng
KW - domination; prism fixer; symmetric dominating set; bipartite graph
UR - http://eudml.org/doc/270301
ER -