PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2004 | 24 | 2 | 303-318
Tytuł artykułu

On the domination number of prisms of graphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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).
Słowa kluczowe
Wydawca
Rocznik
Tom
24
Numer
2
Strony
303-318
Opis fizyczny
Daty
wydano
2004
Twórcy
  • Department of Mathematics and Statistics, University of Victoria, P.O. Box 3045, Victoria, BC Canada V8W 3P4
  • Department of Mathematics and Statistics, University of Victoria, P.O. Box 3045, Victoria, BC Canada V8W 3P4
  • Department of Mathematical Sciences, Indiana University - Purdue University, Fort Wayne, IN 46805, USA
Bibliografia
  • [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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1233
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.