PDF
Discussiones Mathematicae Graph Theory 24(2) (2004)
303-318
DOI: https://doi.org/10.7151/dmgt.1233
ON THE DOMINATION NUMBER OF PRISMS OF GRAPHS
| Alewyn P. Burger and Christina M. Mynhardt
Department of Mathematics and Statistics |
William D. Weakley
Department of Mathematical Sciences |
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
Close