# The Minimal Integral Separator of A Threshold Graph

- Authors
- Publication Date
- Identifiers
- DOI: 10.1016/s0167-5060(08)70749-0
- Disciplines

## Abstract

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.