کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648835 | 1342432 | 2007 | 7 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Dominating direct products of graphs Dominating direct products of graphs](/preview/png/4648835.png)
An upper bound for the domination number of the direct product of graphs is proved. It in particular implies that for any graphs G and H , γ(G×H)⩽3γ(G)γ(H)γ(G×H)⩽3γ(G)γ(H). Graphs with arbitrarily large domination numbers are constructed for which this bound is attained. Concerning the upper domination number we prove that Γ(G×H)⩾Γ(G)Γ(H)Γ(G×H)⩾Γ(G)Γ(H), thus confirming a conjecture from [R. Nowakowski, D.F. Rall, Associative graph products and their independence, domination and coloring numbers, Discuss. Math. Graph Theory 16 (1996) 53–79]. Finally, for paired-domination of direct products we prove that γpr(G×H)⩽γpr(G)γpr(H)γpr(G×H)⩽γpr(G)γpr(H) for arbitrary graphs G and H, and also present some infinite families of graphs that attain this bound.
Journal: Discrete Mathematics - Volume 307, Issue 13, 6 June 2007, Pages 1636–1642