Let G=(V,E) be a simple graph. A subset D of V is called a dominating set of G if for every vertex x∈V-D,x is adjacent to at least one vertex of D . Let γ(G) and γ c(G) denote the ...Let G=(V,E) be a simple graph. A subset D of V is called a dominating set of G if for every vertex x∈V-D,x is adjacent to at least one vertex of D . Let γ(G) and γ c(G) denote the domination and connected domination number of G , respectively. In 1965,Vizing conjectured that if G×H is the Cartesian product of G and H , thenγ(G×H)≥γ(G)·γ(H).In this paper, it is showed that the conjecture holds if γ(H) ≠ γ c(H) .And for paths P m and P n , a lower bound and an upper bound for γ(P m×P n) are obtained.展开更多
文摘Let G=(V,E) be a simple graph. A subset D of V is called a dominating set of G if for every vertex x∈V-D,x is adjacent to at least one vertex of D . Let γ(G) and γ c(G) denote the domination and connected domination number of G , respectively. In 1965,Vizing conjectured that if G×H is the Cartesian product of G and H , thenγ(G×H)≥γ(G)·γ(H).In this paper, it is showed that the conjecture holds if γ(H) ≠ γ c(H) .And for paths P m and P n , a lower bound and an upper bound for γ(P m×P n) are obtained.
