Domination criticality in product graphs (Q896090)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Domination criticality in product graphs
scientific article

    Statements

    Domination criticality in product graphs (English)
    0 references
    0 references
    0 references
    11 December 2015
    0 references
    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\).
    0 references
    Cartesian product
    0 references
    connected domination
    0 references
    grid
    0 references
    critical graphs
    0 references

    Identifiers