User Tools

Site Tools


Richard Behr (Binghamton)

An Introduction to Threshold Graphs

Abstract for the Combinatorics Seminar 2014 April 1

Threshold graphs were first introduced by Chvatal and Hammer to distinguish cliques of a graph in a polydedral representation. A threshold graph is a graph G, for which there exist non-negative real weights wv for each vertex v and a threshold number t, such that for distinct vertices x and y, xy is an edge in G if and only if wx + wy > t. They are important partly because they are “perfect”, but also for other reasons.

I will provide and prove several different characterizations of these graphs, as well as discuss properties of randomly generated threshold graphs, which arise very naturally. I will finish up by discussing a new generalization, now under investigation by Vaidy Sivaraman and me.

seminars/comb/abstract.201404beh.txt · Last modified: 2020/01/29 14:03 (external edit)