On the domination number of cross products of graphs
The cross product \(G\otimes G'\) of two graphs \(G\), \(G'\) is the graph whose vertex set is the Cartesian product of the vertex sets of \(G\) and \(G'\) and in which two vertices \((u, u')\), \((v, v')\) are adjacent if and only if \(u\), \(v\) are adjacent in \(G\) and \(u'\), \(v'\) are adjacent in \(G'\). A subset \(D\) of the vertex set \(V(G)\) of a graph \(G\) is called dominating in \(G\), if for each \(x\in V(G)- D\) there exists a vertex \(y\in D\) adjacent to \(x\). The minimum number of vertices of a dominating set in \(G\) is called the domination number of \(G\). In the paper, the domination number of the cross product \(P_n\otimes P^c_k\) of a path \(P_n\) of length \(n\) with the complement \(P^c_k\) of a path of length \(k\) is found for all values of \(n\) and \(k\). Some corollaries are stated and a conjecture is expressed saying that \(\gamma(G\otimes H)\geq \gamma(G) \gamma(H)\), where \(\gamma\) denotes the domination number.
- A NEW UPPER BOUND FOR THE DOMINATION NUMBER OF A GRAPH
- Bibliography on domination in graphs and some basic definitions of domination parameters
- scientific article; zbMATH DE number 3902703 (Why is no real title available?)
- scientific article; zbMATH DE number 21746 (Why is no real title available?)
- scientific article; zbMATH DE number 1396705 (Why is no real title available?)
- scientific article; zbMATH DE number 3358515 (Why is no real title available?)
- Inequalities between the domination number and the chromatic number of a graph
- On graphs having domination number half their order
- On the domination of the products of graphs II: Trees
- On the domination number of generalized petersen graphs \(P(n,2)\)
- Domination number of the cross product of paths
- Some results on domination number of products of graphs
- Domination in commuting graph and its complement
- On a Vizing-like conjecture for direct product graphs
- \(k\)-tuple total domination in cross products of graphs
- scientific article; zbMATH DE number 2185578 (Why is no real title available?)
- Domination in the cross product of digraphs.
- Connectivity and other invariants of generalized products of graphs
- A note on some domination parameters in graph products
- scientific article; zbMATH DE number 3902703 (Why is no real title available?)
- scientific article; zbMATH DE number 1156590 (Why is no real title available?)
- scientific article; zbMATH DE number 1510634 (Why is no real title available?)
- Domination on Kronecker product of P_n
- scientific article; zbMATH DE number 975402 (Why is no real title available?)
- Smallest independent dominating sets in Kronecker products of cycles
- Explicating the exact \(\gamma_{\mathrm{CD}}\) value for the tensor product of graphs
- Lower bounds for the domination number and the total domination number of direct product graphs
- Dominating direct products of graphs
- On the total domination number of cross products of graphs
This page was built for publication: On the domination number of cross products of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1901047)
