On the 3-${\gamma }_t$-Critical Graphs of Order $\Delta (G)+3$

Abstract

Let ${\gamma }_t(G)$ be the total domination number of graph $G$, a graph $G$ is $k$-total domination vertex critical (or\ just\ $k$-${\gamma }_t$-critical) if ${\gamma }_t(G)=k$, and for any vertex $v$ of $G$ that is not adjacent to a vertex of degree one, ${\gamma }_t(G-v)=k-1$. Mojdeh and Rad \cite{MR06} proposed an open problem: Does there exist a 3-${\gamma }_t$-critical graph $G$ of order $\Delta (G)+3$ with $\Delta (G)$ odd? In this paper, we prove that there exists a 3-${\gamma }_t$-critical graph $G$ of order $\Delta (G)+3$ with odd $\Delta (G)\ge 9$.

This paper was accpted by Utilitas Mathematica in 2008