Discussiones Mathematicae Graph Theory 27(3) (2007)
527-540
doi: 10.7151/dmgt.1377
Richard G. Gibson and Christina M. Mynhardt
Department of Mathematics and Statistics
University of Victoria
P.O. Box 3045, Victoria, BC Canada V8W 3P4
e-mail: richardg@sfu.ca, mynhardt@math.uvic.ca
Hartnell and Rall [On dominating the Cartesian product of a graph and K_{2}, 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_{4} 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.
Keywords: domination, prism fixer, symmetric dominating set, bipartite graph.
2000 Mathematics Subject Classification: 05C69.
[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). |
[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. |
[3] | G. Chartrand and L. Leśniak, Graphs and Digraphs, Third Edition (Chapman & Hall, London, 1996). |
[4] | B.L. Hartnell and D.F. Rall, On Vizing's conjecture, Congr. Numer. 82 (1991) 87-96. |
[5] | B.L. Hartnell and D.F. Rall, On dominating the Cartesian product of a graph and K_{2}, Discuss. Math. Graph Theory 24 (2004) 389-402, doi: 10.7151/dmgt.1238. |
[6] | T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). |
[7] | C.M. Mynhardt and Zhixia Xu, Domination in prisms of graphs: Universal fixers, Utilitas Math., to appear. |
[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. |
[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. |
[11] | V.G. Vizing, Some unsolved problems in graph theory, Uspehi Mat. Nauk 23 (1968) 117-134. |
Received 21 August 2006
Revised 21 February 2007
Accepted 7 March 2007