On a Family of \(4\)-Critical Graphs with Diameter Three

Abstract

A graph \(G\) is \(k\)-total domination edge critical, abbreviated to \(k\)-critical if confusion is unlikely, if the total domination number \(\gamma_t(G)\) satisfies \(\gamma_t(G) = k\) and \(\gamma_t(G + e) < \gamma_t(G)\) for any edge \(e \in E(\overline{G})\).Graphs that are \(4\)-critical have diameter either \(2\), \(3\), or \(4\). In previous papers, we characterized structurally the \(4\)-critical graphs with diameter four and found bounds on the order of \(4\)-critical graphs with diameter two. In this paper, we study a family \(\mathcal{H}\) of \(4\)-critical graphs with diameter three, in which every vertex is a diametrical vertex, and every diametrical pair dominates the graph. We also generalize the self-complementary graphs and show that these graphs provide a special case of the family \(\mathcal{H}\).