Linear separation of totoal dominating sets in graphs

2013-03-25
9:00-10:00
FAMNIT-SEMIN
Nina Chiarelli
Linear separation of totoal 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 corresponding weights exceeds a certain threshold.  These graphs, which we call total domishold graphs, form a non-hereditary class. We also obtain partial results towards a characterisation of graphs in which the above property holds in a hereditary sense.