On the 3-$γ_t$-Critical Graphs of Order $Δ(G)+3$

Abstract

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

This paper was accpted by Utilitas Mathematica in 2008