Give to WPI

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

Stratton Hall

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

Add/Suggest Event | Edit Your Events

Powered by the Social Web - Bringing people together through Events, Places, & Common Interests

  • Email a Friend
  • Bookmark this Page
  • Share this Page