Atlas home || Conferences | Abstracts | about Atlas

22nd Cumberland Conference on Combinatorics, Graph Theory and Computing
May 21-23, 2009
Western Kentucky University
Bowling Green, KY, USA

Organizers
Bela Csaba, Chair; Mustafa Atici; Robert Crawford; Claus Ernst; Dominic Lanphier; Attila Por

View Abstracts
Conference Homepage

Recognition Algorithm for 2-Threshold Graphs
by
Alan P. Sprague
University of Alabama at Birmingham

We say that graph G is a 2-threshold graph with regard to thresholds q1 < q2 if it is possible to assign a rank r(v) to each vertex v, such that vertices v and w are adjacent iff exactly 1 threshold exceeds r(v)+r(w). For example, the sequence of ranks 0, 1, -1, 2, -2, 3, -3, ... shows that every path is a 2-threshold graph with thresholds q1 = -.5 and q2 = 1.5. The classical threshold graphs introduced by Chvatal and Hammer are the analogous case of one threshold. We will discuss a recognition algorithm for 2-threshold graphs. This algorithm is reminiscent of recognition algorithms for bipartite permutation graphs and unit interval graphs.

Date received: April 25, 2009

Copyright © 2009 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cayq-44.