scientific article; zbMATH DE number 1124600
The Cartesian product of two graphs \(G\) and \(H\) with vertex sets \(V(G)\) and \(V(H)\), and edge sets \(E(G)\) and \(E(H)\), respectively, is defined in the following way. The vertex set consists of the normal Cartesian product of \(V(G)\) and \(V(H)\). Then, vertices \((x_1,y_1)\) and \((x_2, y_2)\) in \(V(G)\times V(H)\) are adjacent if \(x_1= x_2\) and \(y_1y_2\in E(H)\), or \(y_1= y_2\) and \(x_1x_2\in E(G)\). The domination number of a graph \(G\) is the cardinality of the smallest set \(A\) such that every vertex of \(G\) is either in \(A\) or adjacent to an element of \(A\). Vizing's conjecture states that the domination number of the Cartesian product of \(G\) and \(H\), is at least as big as the product of the domination numbers of \(G\) and \(H\). This paper surveys the progress and methods of attack on this conjecture, and also mentions some other types of product. The survey is reasonably thorough, though the paper is sometimes unclear due to crucial definitions and notation being omitted. For the entire collection see [Zbl 0883.00011].
- Domination in the hierarchical product and Vizing's conjecture
- Vizing-like conjecture for the upper domination of Cartesian products of graphs -- the proof
- scientific article; zbMATH DE number 2109312
- Domination of generalized Cartesian products
- On total domination in the Cartesian product of graphs
- Total domination of Cartesian products of graphs
- On domination numbers of Cartesian products of paths
- On the total domination number of Cartesian products of graphs
- Domination in digraphs and their direct and Cartesian products
- Power domination of the Cartesian product of graphs
- Vizing's conjecture for chordal graphs
- On symmetric digraphs of the congruence x^k y n
- A result on Vizing's conjecture
- Improving the Clark-Suen bound on the domination number of the Cartesian product of graphs
- Towards a computational proof of Vizing's conjecture using semidefinite programming and sums-of-squares
- Bounding the k-rainbow total domination number
- An improved bound in Vizing's conjecture
- Domination in the hierarchical product and Vizing's conjecture
- Rainbow domination and related problems on strongly chordal graphs
- Alliance free sets in Cartesian product graphs
- On the 2-rainbow domination in graphs
- The structure of digraphs associated with the congruence x k ≡ y (mod n)
- Rainbow domination in graphs
- (Open) packing number of some graph products
- Paired-domination of Cartesian products of graphs and rainbow domination
- Disjoint dominating sets with a perfect matching
- Improving some bounds for dominating Cartesian products
- The Cartesian product of cycles with small 2-rainbow domination number
- The outer-connected vertex edge domination number in Cartesian product graphs
- My top 10 graph theory conjectures and open problems
- On construction for trees making the equality hold in Vizing's conjecture
- Domination in digraphs and their direct and Cartesian products
- A \(\frac{3}{4}\)-approximation of Vizing's conjecture for claw-free graphs
- Thinness of product graphs
- On the domination number of the Cartesian product of the cycle of length n and any graph
- Vizing's conjecture for graphs with domination number 3 -- a new proof
- On the upper total domination number of Cartesian products of graphs
- Rainbow domination on trees
- A survey of selected recent results on total domination in graphs
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4378628)
