首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Dominating direct products of graphs
Authors:Boštjan Brešar  Sandi Klav?ar  Douglas F Rall
Institution:a University of Maribor, FEECS, Smetanova 17, 2000 Maribor, Slovenia
b Department of Mathematics and Computer Science, PeF, University of Maribor, Koroška cesta 160, 2000 Maribor, Slovenia
c Department of Mathematics, Furman University, Greenville, SC, USA
Abstract: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). 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), 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) for arbitrary graphs G and H, and also present some infinite families of graphs that attain this bound.
Keywords:05C69  05C12
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号