PDF

Discussiones Mathematicae Graph Theory 31(1) (2011) 5-23
DOI: https://doi.org/10.7151/dmgt.1526

PAIRED DOMINATION IN PRISMS OF GRAPHS

Christina M. Mynhardt and Mark Schurch

Department of Mathematics and Statistics
University of Victoria
P.O. Box 3060 STN CSC
Victoria, BC, Canada V8W 3R4
e-mail: mynhardt@math.uvic.ca, mschurch@math.uvic.ca

Abstract

The paired domination number γ_pr(G) of a graph G is the smallest cardinality of a dominating set S of G such that áSñ has a perfect matching. The generalized prisms πG of G are the graphs obtained by joining the vertices of two disjoint copies of G by |V(G)| independent edges. We provide characterizations of the following three classes of graphs: γ_pr(πG) = 2γ_pr(G) for all πG; γ_pr(K₂□G) = 2γ_pr(G); γ_pr(K₂□G) = γ_pr(G).

Keywords: domination, paired domination, prism of a graph, Cartesian product.

2010 Mathematics Subject Classification: 05C69.

References

[1]	B. Bresar, M.A. Henning and D.F. Rall, Paired-domination of Cartesian products of graphs, Util. Math. 73 (2007) 255-265.
[2]	A.P. Burger and C.M. Mynhardt, Regular graphs are not universal fixers, Discrete Math. 310 (2010) 364-368, doi: 10.1016/j.disc.2008.09.016.
[3]	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.
[4]	E.J. Cockayne, R.G. Gibson and C.M. Mynhardt, Claw-free graphs are not universal fixers, Discrete Math. 309 (2009) 128-133, doi: 10.1016/j.disc.2007.12.053.
[5]	M. Edwards, R.G. Gibson, M.A. Henning and C.M. Mynhardt, On paired-domination edge critical graphs, Australasian J. Combin. 40 (2008) 279-292.
[6]	R.G. Gibson, Bipartite graphs are not universal fixers, Discrete Math. 308 (2008) 5937-5943, doi: 10.1016/j.disc.2007.11.006.
[7]	B.L. Hartnell and D.F. Rall, On Vizing's conjecture, Congr. Numer. 82 (1991) 87-96.
[8]	B.L. Hartnell and D.F. Rall, On dominating the Cartesian product of a graph and K2, Discuss. Math. Graph Theory 24 (2004) 389-402, doi: 10.7151/dmgt.1238.
[9]	T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998).
[10]	C.M. Mynhardt and Z. Xu, Domination in prisms of graphs: Universal fixers, Utilitas Math. 78 (2009) 185-201.
[11]	M. Schurch, Domination Parameters for Prisms of Graphs (Master's thesis, University of Victoria, 2005).

Received 29 January 2009
Revised 27 July 2009
Accepted 27 July 2009