pith. sign in

arxiv: 1109.0707 · v2 · pith:4OZUWTIYnew · submitted 2011-09-04 · 🧮 math.CO

A brief, simple proof of Vizing's conjecture

classification 🧮 math.CO
keywords gammaconjecturesquarevizingbriefcalledcardinalitycartesian
0
0 comments X
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.