**Problem of the Week**

**BUGCAT**

**Zassenhaus Conference**

**Hilton Memorial Lecture**

**BingAWM**

**Math Club**

**Actuarial Association**

You are here: Homepage » Seminars - Academic year 2023-24 » Combinatorics Seminar » Richard Behr (Binghamton)

seminars:comb:abstract.201404beh

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 w_{v} 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 w_{x} + w_{y} > 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)

Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Noncommercial-Share Alike 3.0 Unported