Affordable Access

Publisher Website

The Minimal Integral Separator of A Threshold Graph

Publication Date
DOI: 10.1016/s0167-5060(08)70749-0
  • Computer Science


A graph is called threshold if there exists a real number b and real numbers a j associated with its vertices w j such that Σ a j ≤ b holds iff S is a stable (independent) set of vertices. The vector 〈 a 1,…, a n; b〉 associated to a threshold graph is called an integral separator if a i + a j ≥ b + 1 for every edge ( w i w j ). A simple algorithm is presented to determine for a given threshold graph its (unique) integral separator which minimizes b.

There are no comments yet on this publication. Be the first to share your thoughts.