Paired domination in prisms of graphs

Christina M. Mynhardt; Mark Schurch

Discussiones Mathematicae Graph Theory, Tome 31 (2011), p. 5-23 / Harvested from The Polish Digital Mathematics Library

Résumé

The paired domination number $γ_{p r} (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: $γ_{p r} (π G) = 2 γ_{p r} (G)$ for all πG; $γ_{p r} (K ₂ ☐ G) = 2 γ_{p r} (G)$ ; $γ_{p r} (K ₂ ☐ G) = γ_{p r} (G)$ .

Publié le : 2011-01-01

Zbl 1238.05201

EUDML-ID : urn:eudml:doc:270903

@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1526,
     author = {Christina M. Mynhardt and Mark Schurch},
     title = {Paired domination in prisms of graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {31},
     year = {2011},
     pages = {5-23},
     zbl = {1238.05201},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1526}
}

Christina M. Mynhardt; Mark Schurch. Paired domination in prisms of graphs. Discussiones Mathematicae Graph Theory, Tome 31 (2011) pp. 5-23. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1526/

Bibliographie

[000] [1] B. Bresar, M.A. Henning and D.F. Rall, Paired-domination of Cartesian products of graphs, Util. Math. 73 (2007) 255-265. | Zbl 1161.05053

[001] [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. | Zbl 1216.05098

[002] [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. | Zbl 1064.05111

[003] [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. | Zbl 1219.05116

[004] [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. | Zbl 1169.05032

[005] [6] R.G. Gibson, Bipartite graphs are not universal fixers, Discrete Math. 308 (2008) 5937-5943, doi: 10.1016/j.disc.2007.11.006. | Zbl 1181.05068

[006] [7] B.L. Hartnell and D.F. Rall, On Vizing's conjecture, Congr. Numer. 82 (1991) 87-96. | Zbl 0764.05092

[007] [8] 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. | Zbl 1063.05107

[008] [9] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). | Zbl 0890.05002

[009] [10] C.M. Mynhardt and Z. Xu, Domination in prisms of graphs: Universal fixers, Utilitas Math. 78 (2009) 185-201. | Zbl 1284.05199

[010] [11] M. Schurch, Domination Parameters for Prisms of Graphs (Master's thesis, University of Victoria, 2005).