On the existence problem of the total domination vertex critical graphs

The existence problem of the total domination vertex critical graphs has been studied in a series of articles. We first settle the existence problem with respect to the parities of the total domination number mm and the maximum degree ΔΔ: for even mm except m=4m=4, there is no mm-γtγt-critical graph regardless of the parity of ΔΔ; for m=4m=4 or odd m≥3m≥3 and for even ΔΔ, an mm-γtγt-critical graph exists if and only if Δ≥2⌊m−12⌋; for m=4m=4 or odd m≥3m≥3 and for odd ΔΔ, if Δ≥2⌊m−12⌋+7, then mm-γtγt-critical graphs exist, if Δ<2⌊m−12⌋, then mm-γtγt-critical graphs do not exist. The only remaining open cases are Δ=2⌊m−12⌋+k, k=1,3,5k=1,3,5. Second, we study these remaining open cases when m=4m=4 or odd m≥9m≥9. As the previously known result for m=3m=3, we also show that for Δ(G)=3,5,7Δ(G)=3,5,7, there is no 44-γtγt-critical graph of order Δ(G)+4Δ(G)+4. On the contrary, it is shown that for odd m≥9m≥9 there exists an mm-γtγt-critical graph for all Δ≥m−1Δ≥m−1.