ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory


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


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


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(K2□G) = 2γpr(G); γpr(K2□G) = γpr(G).

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

2010 Mathematics Subject Classification: 05C69.


[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