Linear Separation of Total Dominating Sets in Graphs

摘要

A total dominating set in a graph is a set of vertices such that every vertex of the graph has a neighbor in the set. We introduce and study graphs that admit non-negative real weights associated to their vertices so that a set of vertices is a total dominating set if and only if the sum of the corresponding weights exceeds a certain threshold. We show that these graphs, which we call total domishold graphs, form a non-hereditary class of graphs properly containing the classes of threshold graphs and the complements of domishold graphs. We present a polynomial time recognition algorithm of total domishold graphs, and obtain partial results towards a characterization of graphs in which the above property holds in a hereditary sense. Our characterization in the case of split graphs is obtained by studying a new family of hypergraphs, defined similarly as the Sperner hypergraphs, which may be of independent interest.