# Counterexample to a conjecture on the structure of bipartite partitionable graphs

Richard G. Gibson; Christina M. Mynhardt

Discussiones Mathematicae Graph Theory (2007)

- Volume: 27, Issue: 3, page 527-540
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topRichard 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 -

## References

top- [1] D.W. Bange, A.E. Barkauskas and P.J. Slater, Efficient dominating sets in graphs, in: R.D. Ringeisen and F.S. Roberts, eds, Applications of Discrete Mathematics 189-199 (SIAM, Philadelphia, PA, 1988). Zbl0664.05027
- [2] A.P. Burger, C.M. Mynhardt and W.D. Weakley, On the domination number of prisms of graphs, Discuss. Math. Graph Theory 24 (2004) 303-318, doi: 10.7151/dmgt.1233. Zbl1064.05111
- [3] G. Chartrand and L. Leśniak, Graphs and Digraphs, Third Edition (Chapman & Hall, London, 1996). Zbl0890.05001
- [4] B.L. Hartnell and D.F. Rall, On Vizing's conjecture, Congr. Numer. 82 (1991) 87-96. Zbl0764.05092
- [5] B.L. Hartnell and D.F. Rall, On dominating the Cartesian product of a graph and K₂, Discuss. Math. Graph Theory 24 (2004) 389-402, doi: 10.7151/dmgt.1238. Zbl1063.05107
- [6] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). Zbl0890.05002
- [7] C.M. Mynhardt and Zhixia Xu, Domination in prisms of graphs: Universal fixers, Utilitas Math., to appear. Zbl1284.05199
- [8] P.R.J. Östergå rd and W.D. Weakley, Classification of binary covering codes, J. Combin. Des. 8 (2000) 391-401, doi: 10.1002/1520-6610(2000)8:6<391::AID-JCD1>3.0.CO;2-R Zbl0989.94037
- [9] M. Schurch, Domination Parameters for Prisms of Graphs (Master's thesis, University of Victoria, 2005).
- [10] C.B. Smart and P.J. Slater, Complexity results for closed neighborhood order parameters, Congr. Numer. 112 (1995) 83-96. Zbl0895.05060
- [11] V.G. Vizing, Some unsolved problems in graph theory, Uspehi Mat. Nauk 23 (1968) 117-134. Zbl0177.52301

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.