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.


Seen <100 times

More articles like this

Minimal vertex separators of chordal graphs

on Discrete Applied Mathematics Jan 01, 1998

Minimal separators in [formula omitted]-tidy graph...

on Electronic Notes in Discrete M... Jan 01, 2009

Minimal separators of 2-chordal graphs

on Linear Algebra and its Applica... Jan 01, 1993
More articles like this..