Dominating direct products of graphs
Let \(G=(V,E)\) be a graph. A set \(S\subset V\) is called dominating if each vertex in \(V\backslash S\) is adjacent to at least one vertex in \(S\). The domination number \(\gamma(G)\) of a graph \(G\) is the minimum cardinality of a dominating set. For graphs \(G\) and \(H\), the direct product \(G\times H\) is the graph with vertex set \(V(G)\times V(H)\) where two vertices \((x,y)\) and \((v,w)\) are adjacent if and only if \(xv\in E(G)\) and \(yw\in E(H)\). The purpose of the paper is to estimate the domination number and some related parameters (upper domination number and paired-domination number) of a direct product of graphs. Two of the main results are: (1) \(\gamma(G\times H)\leq 3\gamma(G)\gamma(H)\). (2) Graphs with arbitrarily large domination numbers for which there is an equality in this inequality are constructed.
- A note on domination parameters of the conjunction of two special graphs
- Associative graph products and their independence, domination and coloring numbers
- Domination number of the cross product of paths
- scientific article; zbMATH DE number 3172309 (Why is no real title available?)
- scientific article; zbMATH DE number 139936 (Why is no real title available?)
- scientific article; zbMATH DE number 1095171 (Why is no real title available?)
- scientific article; zbMATH DE number 1510634 (Why is no real title available?)
- scientific article; zbMATH DE number 1792590 (Why is no real title available?)
- scientific article; zbMATH DE number 2108130 (Why is no real title available?)
- scientific article; zbMATH DE number 1398657 (Why is no real title available?)
- scientific article; zbMATH DE number 2192181 (Why is no real title available?)
- On a Vizing-like conjecture for direct product graphs
- On the domination number of cross products of graphs
- Paired-domination in graphs
- Smallest independent dominating sets in Kronecker products of cycles
- Some results on total domination in direct products of graphs
- Total Domination in Categorical Products of Graphs
- Vizing-like conjecture for the upper domination of Cartesian products of graphs -- the proof
- A polynomial-time algorithm for the paired-domination problem on permutation graphs
- Domination and upper domination of direct product graphs
- Dominating sets in intersection graphs of finite groups
- On the domination number of cross products of graphs
- On a Vizing-like conjecture for direct product graphs
- Tightness of domination inequalities for direct product graphs
- Domination parameters of the unitary Cayley graph of \(\mathbb{Z}/n \mathbb{Z} \)
- Domination in direct products of complete graphs
- On well-dominated graphs
- On independent domination in direct products
- On the power domination number of graph products
- Graph products and integer domination. II
- Connectivity and other invariants of generalized products of graphs
- Paired domination in graphs
- On the roman domination in the lexicographic product of graphs
- Some results on total domination in direct products of graphs
- Domination-related parameters in rooted product graphs
- Unimodality and monotonic portions of certain domination polynomials
- Domination number of modular product graphs
- Lower bounds for the domination number and the total domination number of direct product graphs
- Bounds on the domination number and the metric dimension of co-normal product of graphs
- Idomatic partitions of direct products of complete graphs
This page was built for publication: Dominating direct products of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q879339)
