Domination criticality in product graphs

Abstract

A connected dominating set is an important notion and has many applications in routing and management of networks. Graph products have turned out to be a good model of interconnection networks. This motivated us to study the Cartesian product of graphs G with connected domination number, γc(G)=2,3 and characterize such graphs. Also, we characterize the k−γ-vertex (edge) critical graphs and k−γc-vertex (edge) critical graphs for k=2,3 where γ denotes the domination number of G. We also discuss the vertex criticality in grids.

Keywords

• Cartesian product
• Connected domination
• Grid
• Critical graphs