Difference graphs (Q5895304): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Threshold characterization of graphs with dilworth number two / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3941433 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4165164 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5514188 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Threshold Sequences / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The splittance of a graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Extreme degree sequences of simple graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Inequalities: theory of majorization and its applications / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The polytope of degree sequences / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3929766 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3851094 / rank | |||
Normal rank |
Revision as of 13:12, 21 June 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