Bounds on the order of 4-critical graphs with diameter two

Abstract

Let γt(G) denote the total domination number of the graph G. G is said to be total domination edge critical, or simply γt-critical, if γt(G + e) < γt(G) for each edge e ε E(Ḡ). The diameter of 4-critical graphs is either 2, 3 or 4. In a previous paper we characterized the 4-critical graphs with diameter four. In this paper we study graphs with diameter two, and give bounds on the number of vertices in 4-critical graphs with diameter two.