Difference graphs (Q5895304)

A graph \(G=(V,E)\) is said to be a difference graph if there exist real numbers \(a_ 1,a_ 2,...,a_ n\) associated with the vertices of G and a positive real number T such that (1) \(| a_ i| <T\) for \(i=1,2,...,n\); (2) distinct vertices i and j are adjacent if and only if \(| a_ i-a_ j| >=T\). It can be shown that difference graphs are bipartite. Also properties of threshold graphs can easily be extended to difference graphs. More important the authors describe the polytope of bipartite degree sequences with a given bipartition, and show that its extreme points are exactly the degree sequences of the difference graphs with the same bipartition. Finally they give a polynomial time algorithm to recognize potentially difference degree sequences when the bipartition is unknown. This partly solves the problem of recognizing potentially bipartite-graphic degree sequences, see [\textit{S. B. Rao}, Combinatorics and Graph Theory, Proc. Symp., Calcutta 1980, Lect. Notes Math. 885 (1981; Zbl 0474.05043)].