Matchings and Path Covers with applications to Domination in Graphs

Abstract

Let $G$ be a graph with no isolated vertex. A matching in $G$ is a set of edges that are pairwise not adjacent in $G$, while the matching number, ${\alpha }^{\prime }(G)$, of $G$ is the maximum size of a matching in $G$. The path covering number, $\mathrm{pc}(\mathrm{G})$, of $G$ is the minimum number of vertex disjoint paths such that every vertex belongs to a path in the cover. We show that if $G$ has order $n$, then ${\alpha }^{\prime }(G)+\frac{1}{2}\mathrm{pc}(\mathrm{G})\ge \frac{\mathrm{n}}{2}$ and we provide a constructive characterization of the graphs achieving equality in this bound. It is known that $\gamma (G)\le {\alpha }^{\prime }(G)$ and ${\gamma }_t(G)\le {\alpha }^{\prime }(G)+\mathrm{pc}(\mathrm{G})$, where $\gamma (G)$ and ${\gamma }_t(G)$ denote the domination and the total domination number of $G$. As an application of our result on the matching and path cover numbers, we show that if $G$ is a graph with $\delta (G)\ge 3$, then ${\gamma }_t(G)\le {\alpha }^{\prime }(G)+\frac{1}{2}(\mathrm{pc}(\mathrm{G})-1)$, and this bound is tight. A set $S$ of vertices in $G$ is a neighborhood total dominating set of $G$ if it is a dominating set of $G$ with the property that the subgraph induced by the open neighborhood of the set $S$ has no isolated vertex. The neighborhood total domination number, ${\gamma }_{\mathrm{nt}}(G)$, is the minimum cardinality of a neighborhood total dominating set of $G$. We observe that $\gamma (G)\le {\gamma }_{\mathrm{nt}}(G)\le {\gamma }_t(G)$. As a further application of our result on the matching and path cover numbers, we show that if $G$ is a connected graph on at least six vertices, then ${\gamma }_{\mathrm{nt}}(G)\le {\alpha }^{\prime }(G)+\frac{1}{2}\mathrm{pc}(\mathrm{G})$ and this bound is tight.