Difference graphs (Q5895304): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 11:25, 30 January 2024
scientific article; zbMATH DE number 4179411
Language | Label | Description | Also known as |
---|---|---|---|
English | Difference graphs |
scientific article; zbMATH DE number 4179411 |
Statements
Difference graphs (English)
0 references
1990
0 references
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)].
0 references
difference graph
0 references
threshold graphs
0 references