Equality in Vizing’s Conjecture Fixing One Factor of the Cartesian Product

S. M. Khamis- Kh. M. Nazzal ; Khamis, Soheir 


In this paper, we investigate the existence of nontrivial solutions for the equation γ(G□H) = γ(G) γ(H) fixing one factor. For the complete bipartite graphs Km,n; we characterize all nontrivial solutions when m = 2, n ≥ 3 and prove the nonexistence of solutions when m, n ≥ 3. In addition, it is proved that the above equation has no nontrivial solution if H is one of the graphs obtained from Cn, the cycle of length n, either by adding a vertex and one pendant edge joining this vertex to any v ∈ V(Cn), or by adding one chord joining two alternating vertices of Cn .

Other data

Keywords Domination number, Cartesian product, Vizing’s conjecture
Issue Date 2010
URI http://research.asu.edu.eg/123456789/1130

File Description SizeFormat 
Equality in Vizing’s Conjecture.pdf251.8 kBAdobe PDFView/Open
Recommend this item

CORE Recommender


Items in Ain Shams Scholar are protected by copyright, with all rights reserved, unless otherwise indicated.