Colloquium-Martin Milanic (University of Primorska, Koper, Slovenia)-Linear Separation of Connected Dominating Sets in Graphs
Mathematics - Colloquium
Thursday, January 9, 2014
11:00 AM-12:00 PM
ABSTRACT: A connected dominating set in a graph is a dominating set of vertices that induces a connected subgraph. We introduce and study the class of connected-domishold graphs, which are graphs that admit non-negative real weights associated to their vertices such that a set of vertices is a connected dominating set if and only if the sum of the corresponding weights exceeds a certain threshold. We show that these graphs form a non-hereditary class of graphs properly containing two well known classes of chordal graphs: block graphs and trivially perfect graphs. We characterize, in several ways, the graphs every induced subgraph of which is connected-domishold: in terms of forbidden induced subgraphs, in terms of 2asummability of certain derived Boolean functions, and in terms of the dually Sperner property of certain derived hypergraphs. Joint work with Nina Chiarelli.
Suggested Audiences: College, Adult
Last Modified: January 7, 2014 at 2:30 PM