Domination criticality in product graphs
type: Item
instance of: scholarly article
title: Domination criticality in product graphs
zbMATH Open document ID: 1360.05134
author: M. R. Chithra
author: A. Vijayakumar
published in: AKCE International Journal of Graphs and Combinatorics
publication date: 2015-12-11T00:00:00Z
review text: Let \(G=(V,E)\) be a simple graph. A subset \(S\) of vertices of \(G\) is a dominating set if \(N[S]=V\) and is a connected dominating set if the induced subgraph \(G[S]\) is connected. The (connected) domination number \(\gamma(G) \) (\(\gamma_c(G)\)) is the minimum cardinality of a (connected) dominating set of \(G\). A graph \(G\) is \(k\mathrm{-}P\)-edge critical if \(P(G) = k\) and \(P(G + e) < k\) for each edge \(e\not \in E(G)\) and \(G\) is \(k-P\)-vertex critical if \(P(G) = k\) but for each vertex \(v\in G\), \(P(G - v) < k\) where \(P\in\{\gamma,\gamma_c\}\). The Cartesian product \(G\square H\) of two graphs \(G\) and \(H\) is the graph with vertex set \(V(G)\times V(H)\) and two vertices \((u_i,v_j) , (u_x,v_y)\) are adjacent if either \(u_i = u_x\) and \(v_jv_y\in E(H)\) or \(u_iu_x\in E(G)\) and \(v_j = v_y\). In this paper, the authors characterized all Cartesian product graphs \(G\) with \(\gamma_{c}(G) = 2, 3\). Also, they characterized the \(k-\gamma\)-vertex (edge) critical graphs and \(k-\gamma_c\)-vertex (edge) critical graphs for \(k = 2, 3\). The main results of this paper are: Let \(G=H_1\square H_2\) be a connected graph. Then \(G\) is \(2\mathrm{-}\gamma\)-vertex (edge) critical if and only if \(G=C_4\). Let \(G=H_1\square H_2\) be a connected graph. Then \(G\) is \(2\mathrm{-}\gamma_c\)-vertex (edge) critical if and only if \(G=C_4\). Let \(G=H_1\square H_2\) be a connected graph. Then \(G\) is \(3\mathrm{-}\gamma\)-vertex (edge) critical if and only if \(H_1=H_2=K_3\). Let \(G=H_1\square H_2\) be a connected graph. Then \(G\) is \(3\mathrm{-}\gamma_c\)-vertex (edge) critical if and only if \(H_1=H_2=K_3\).
Mathematics Subject Classification ID: 05C76
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 6520411
zbMATH Keywords: Cartesian product
zbMATH Keywords: connected domination
zbMATH Keywords: grid
zbMATH Keywords: critical graphs
reviewed by: Seyed Mahmood Sheikholeslami
MaRDI profile type: Publication
full work available at URL: j.akcej.2015.06.003
OpenAlex ID: W1440088849
cites work: Q4435203
cites work: Q4368728
cites work: Structural Analysis of Complex Networks
cites work: Q5302113
cites work: Domination critical graphs
cites work: Connected domination critical graphs.
cites work: Vertex domination-critical graphs
cites work: Some properties of 3-domination-critical graphs
cites work: Connected domination: vertex criticality and matchings
cites work: The Domination Number of Grids
cites work: THE DIAMETER VARIABILITY OF THE CARTESIAN PRODUCT OF GRAPHS
DOI: 10.1016/J.AKCEJ.2015.06.003
description: scientific article; zbMATH DE number 6520411