DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

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

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 24(2) (2004) 303-318
DOI: 10.7151/dmgt.1233

ON THE DOMINATION NUMBER OF PRISMS OF GRAPHS

Alewyn P. Burger and Christina M. Mynhardt

Department of Mathematics and Statistics
University of Victoria
P.O. Box 3045, Victoria, BC Canada V8W 3P4

e-mail: alewyn@math.uvic.ca
e-mail: mynhardt@math.uvic.ca

William D. Weakley

Department of Mathematical Sciences
Indiana University - Purdue University
Fort Wayne, IN 46805, USA

e-mail: weakley@ipfw.edu

Abstract

For a permutation π of the vertex set of a graph G, the graph πG is obtained from two disjoint copies G1 and G2 of G by joining each v in G1 to π(v) in G2. Hence if π = 1, then πG = K2×G, the prism of G. Clearly, γ(G) ≤ γ(πG) ≤ 2 γ(G). We study graphs for which γ (K2×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).

Keywords: domination, graph products, prisms of graphs.

2000 Mathematics Subject Classification: 05C69.

References

[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.
[2] N.L. Biggs, Algebraic Graph Theory, Second Edition (Cambridge University Press, Cambridge, England, 1996).
[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.
[4] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998).
[5] S.M. Johnson, A new lower bound for coverings by rook domains, Utilitas Mathematica 1 (1972) 121-140.
[6] O. Ore, Theory of Graphs, Amer. Math. Soc. Colloq. Publ. 38 (Amer. Math. Soc., Providence, RI, 1962).
[7] F.S. Roberts, Applied Combinatorics (Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1984).
[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.

Received 1 October 2002
Revised 29 April 2003