PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2004 | 24 | 3 | 389-402
Tytuł artykułu

On dominating the Cartesian product of a graph and K₂

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
In this paper we consider the Cartesian product of an arbitrary graph and a complete graph of order two. Although an upper and lower bound for the domination number of this product follow easily from known results, we are interested in the graphs that actually attain these bounds. In each case, we provide an infinite class of graphs to show that the bound is sharp. The graphs that achieve the lower bound are of particular interest given the special nature of their dominating sets and are investigated further.
Słowa kluczowe
Wydawca
Rocznik
Tom
24
Numer
3
Strony
389-402
Opis fizyczny
Daty
wydano
2004
otrzymano
2003-01-20
poprawiono
2004-03-30
Twórcy
  • Saint Mary's University, Halifax, Nova Scotia, Canada B3H 3C3
  • Furman University, Greenville, SC 29613 USA
Bibliografia
  • [1] W.E. Clark and S. Suen, An inequality related to Vizing's conjecture, Elec. J. of Comb. 7 (#N4) (2000) 1-3.
  • [2] M. El-Zahar and C.M. Pareek, Domination number of products of graphs, Ars Combin. 31 (1991) 223-227.
  • [3] B.L. Hartnell and D.F. Rall, On Vizing's conjecture, Congr. Numer. 82 (1991) 87-96.
  • [4] B.L. Hartnell and D.F. Rall, Lower bounds for dominating Cartesian products, J. Comb. Math. Comb. Comp. 31 (1999) 219-226.
  • [5] B.L. Hartnell and D.F. Rall, Improving some bounds for dominating Cartesian products, Discuss. Math. Graph Theory 23 (2003) 261-272, doi: 10.7151/dmgt.1201.
  • [6] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs, Monographs and Textbooks in Pure and Applied Mathematics, Vol. 208, Marcel Dekker, Inc., New York, 1998.
  • [7] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics, Monographs and Textbooks in Pure and Applied Mathematics, Vol. 209, Marcel Dekker, Inc., New York, 1998.
  • [8] W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 2000.
  • [9] M.S. Jacobson and L.F. Kinch, On the domination number of products of graphs: I, Ars Combin. 18 (1983) 33-44.
  • [10] M.S. Jacobson and L.F. Kinch, On the domination of the products of graphs II: trees, J. Graph Theory 10 (1986) 97-106, doi: 10.1002/jgt.3190100112.
  • [11] V.G. Vizing, The Cartesian product of graphs, Vycisl. Sistemy 9 (1963) 30-43.
  • [12] V.G. Vizing, Some unsolved problems in graph theory, Uspehi Mat. Nauk 23 no. 6(144) (1968) 117-134.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1238
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ć.