# On the domination number of prisms of graphs

Alewyn P. Burger; Christina M. Mynhardt; William D. Weakley

Discussiones Mathematicae Graph Theory (2004)

- Volume: 24, Issue: 2, page 303-318
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topAlewyn P. Burger, Christina M. Mynhardt, and William D. Weakley. "On the domination number of prisms of graphs." Discussiones Mathematicae Graph Theory 24.2 (2004): 303-318. <http://eudml.org/doc/270590>.

@article{AlewynP2004,

abstract = {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).},

author = {Alewyn P. Burger, Christina M. Mynhardt, William D. Weakley},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {domination; graph products; prisms of graphs},

language = {eng},

number = {2},

pages = {303-318},

title = {On the domination number of prisms of graphs},

url = {http://eudml.org/doc/270590},

volume = {24},

year = {2004},

}

TY - JOUR

AU - Alewyn P. Burger

AU - Christina M. Mynhardt

AU - William D. Weakley

TI - On the domination number of prisms of graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2004

VL - 24

IS - 2

SP - 303

EP - 318

AB - 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).

LA - eng

KW - domination; graph products; prisms of graphs

UR - http://eudml.org/doc/270590

ER -

## References

top- [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. Zbl1054.94022
- [2] N.L. Biggs, Algebraic Graph Theory, Second Edition (Cambridge University Press, Cambridge, England, 1996). Zbl0284.05101
- [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). Zbl0890.05002
- [5] S.M. Johnson, A new lower bound for coverings by rook domains, Utilitas Mathematica 1 (1972) 121-140. Zbl0265.05011
- [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. Zbl0653.94014

## Citations in EuDML Documents

top- Matthew Walsh, Fractional domination in prisms
- Christina M. Mynhardt, Mark Schurch, Paired domination in prisms of graphs
- Richard G. Gibson, Christina M. Mynhardt, Counterexample to a conjecture on the structure of bipartite partitionable graphs
- Stephen Benecke, Christina M. Mynhardt, Characterizing Cartesian fixers and multipliers
- Magdalena Lemańska, Rita Zuazua, Convex universal fixers
- Linda Eroh, Ralucca Gera, Cong X. Kang, Craig E. Larson, Eunjeong Yi, Domination in functigraphs