A brief, simple proof of Vizing's conjecture
classification
🧮 math.CO
keywords
gammaconjecturesquarevizingbriefcalledcardinalitycartesian
read the original abstract
For any graph $G=(V,E)$, a subset $S\subseteq V$ \emph{dominates} $G$ if all vertices are contained in the closed neighborhood of $S$, that is $N[S]=V$. The minimum cardinality over all such $S$ is called the domination number, written $\gamma(G)$. In 1963, V.G. Vizing conjectured that $\gamma(G \square H) \geq \gamma(G)\gamma(H)$ where $\square$ stands for the Cartesian product of graphs. In this note, we prove the conjecture.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.