Lower bounds on the total domination number of a graph

摘要

A set S of vertices in a graph G is a total dominating set if every vertex of G is adjacent to a vertex in S. The minimum cardinality of a total dominating set of G is the total domination number of G. Much interest in total domination in graphs has arisen from a computer program Graffiti. pc that has generated several hundred conjectures on total domination (see http://cms.dt.uh.edu/faculty/delavinae/research/wowII). We prove and disprove some conjectures from Graffiti. pc concerning lower bounds on the total domination number of a graph.