Regular totally domatically full graphs
The total domatic number \(d_ t(G)\) of a graph \(G\) was studied by \textit{R. B. Allan, R. Laskar} and \textit{St. Hedetniemi} [Discrete Math. 49, 7-13 (1984; Zbl 0576.05028)]. Let \(md(G)\) be the minimum degree of a vertex in \(G\). A graph \(G\) is said to be totally domatically full if \(d_ t(G)=md(G)\). By a uniquely total domatic graph the author means a graph \(G\) in which exists exactly one total domatic partition with \(d_ t(G)\) classes. First, he considers bipartite graphs. Among other things he shows that no bipartite graph \(G\) with \(d_ t(G)\geq 2\) is uniquely totally domatic. A weaker concept called quasi-uniquely totally domatic graph is introduced and turns out to be useful in the study of directed graphs. Further the parameter \(d_ t(G)\) is transferred to digraphs. For instance it is shown that for positive integers \(k,n\), \(n\geq 3k\), there exists a tournament \(T\) of order \(n\) such that \(d_ t(T)=k\).
scientific article; zbMATH DE number 8140