Contents

Connected Graphs with Maximum Total Domination Number

Robert C. Brigham1, Julie R. Carrington2, Richard P. Vitray2
1Department of Mathematics University of Central Florida Orlando FL 32816
2Department of Mathematical Sciences Rollins College Winter Park FL 32789

Abstract

The total domination number \(\gamma_t(G)\) of graph \(G = (V, E)\) is the cardinality of a smallest subset \(S\) of \(V\) such that every vertex of \(V\) has a neighbor in \(S\). It is known that, if \(G\) is a connected graph with \(n\) vertices, \(\gamma_t(G) \leq \left\lfloor{2n}/{3}\right\rfloor\). Graphs achieving this bound are characterized.