Domination Number in Graphs with Minimum Degree Two

(整期优先)网络出版时间:2009-08-18
/ 1
AsetDofverticesofagraphG=(V,E)iscalledadominatingsetifeveryvertexofVnotinDisadjacenttoavertexofD.In1996,Reedprovedthateverygraphofordernwithminimumdegreeatleast3hasadominatingsetofcardinalityatmost3n/8.InthispaperwegeneralizeReed'sresult.WeshowthateverygraphGofordernwithminimumdegreeatleast2hasadominatingsetofcardinalityatmost(3n+|V_2|)/8,whereV_2denotesthesetofverticesofdegree2inG.Asanapplicationoftheaboveresult,weshowthatfork>1,thek-restricteddominationnumberr_k(G,y)<(3n+5k)/8forallgraphsofordernwithminimumdegreeatleast3.