For a permutation π of the vertex set of a graph G, the graph π G is obtained from two disjoint copies G₁ and G₂ of G by joining each v in G₁ to π(v) in G₂. Hence if π = 1, then πG = K₂×G, the prism of G. Clearly, γ(G) ≤ γ(πG) ≤ 2 γ(G). We study graphs for which γ(K₂×G) = 2γ(G), those for which γ(πG) = 2γ(G) for at least one permutation π of V(G) and those for which γ(πG) = 2γ(G) for each permutation π of V(G).
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1233,
author = {Alewyn P. Burger and Christina M. Mynhardt and William D. Weakley},
title = {On the domination number of prisms of graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {24},
year = {2004},
pages = {303-318},
zbl = {1064.05111},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1233}
}
Alewyn P. Burger; Christina M. Mynhardt; William D. Weakley. On the domination number of prisms of graphs. Discussiones Mathematicae Graph Theory, Tome 24 (2004) pp. 303-318. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1233/
[000] [1] R. Bertolo, P.R.J. Ostergard and W.D. Weakley, An Updated Table of Binary/Ternary Mixed Covering Codes, J. Combin. Design, to appear. | Zbl 1054.94022
[001] [2] N.L. Biggs, Algebraic Graph Theory, Second Edition (Cambridge University Press, Cambridge, England, 1996). | Zbl 0284.05101
[002] [3] N.L. Biggs, Some odd graph theory, Ann. New York Acad. Sci. 319 (1979) 71-81, doi: 10.1111/j.1749-6632.1979.tb32775.x.
[003] [4] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). | Zbl 0890.05002
[004] [5] S.M. Johnson, A new lower bound for coverings by rook domains, Utilitas Mathematica 1 (1972) 121-140. | Zbl 0265.05011
[005] [6] O. Ore, Theory of Graphs, Amer. Math. Soc. Colloq. Publ. 38 (Amer. Math. Soc., Providence, RI, 1962).
[006] [7] F.S. Roberts, Applied Combinatorics (Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1984).
[007] [8] G.J.M. Van Wee, Improved Sphere Bounds On The Covering Radius Of Codes, IEEE Transactions on Information Theory 2 (1988) 237-245, doi: 10.1109/18.2632. | Zbl 0653.94014