pith. sign in

arxiv: 1512.01077 · v2 · pith:4OHLCUENnew · submitted 2015-12-03 · 🧮 math.CO

A class of graphs approaching Vizing's conjecture

classification 🧮 math.CO
keywords gammaclassgraphgraphsmathcalsquarevizingapproaching
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 define classes of graphs $\mathcal{A}_n$, for $n\geq 0$, so that every graph belongs to some such class, and $\mathcal{A}_0$ corresponds to class $A$ of Bartsalkin and German. We prove that for any graph $G$ in class $\mathcal{A}_1$, $\gamma(G\square H)\geq \left(\gamma(G)-\sqrt{\gamma(G)}\right)\gamma(H)$.

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.