Difference graphs
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)].
- Extreme degree sequences of simple graphs
- scientific article; zbMATH DE number 3182201 (Why is no real title available?)
- scientific article; zbMATH DE number 3743297 (Why is no real title available?)
- scientific article; zbMATH DE number 3758364 (Why is no real title available?)
- scientific article; zbMATH DE number 3598234 (Why is no real title available?)
- scientific article; zbMATH DE number 3225808 (Why is no real title available?)
- Inequalities: theory of majorization and its applications
- The polytope of degree sequences
- The splittance of a graph
- Threshold characterization of graphs with dilworth number two
- Threshold Sequences
- Note on upper bound graphs and forbidden subposets
- Weighted coloring on planar, bipartite and split graphs: Complexity and approximation
- Probe threshold and probe trivially perfect graphs
- Degree sequences and majorization
- Well-graded families of relations
- Decompositions for the edge colouring of reduced indifference graphs.
- On variations of \(P_{4}\)-sparse graphs
- Induced matchings in asteroidal triple-free graphs
- (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization.
- Estimating parameters of a probabilistic heterogeneous block model via the EM algorithm
- The maximum cardinality cut problem in co-bipartite chain graphs
- Chordal bipartite graphs of bounded tree- and clique-width
- Enumeration of difference graphs
- Properties of random difference graphs
- On difference graphs and the local dimension of posets
- On the second largest normalized Laplacian eigenvalue of graphs
- Equimatchable bipartite graphs
- On bipartite graphs having minimum fourth adjacency coefficient
- Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs
- Graph clustering via generalized colorings
- On pairwise compatibility graphs having Dilworth number k
- On the strong chromatic index and maximum induced matching of tree-cographs, permutation graphs and chordal bipartite graphs
- The complexity of the defensive domination problem in special graph classes
- Vertex types in threshold and chain graphs
- Fast algorithms for computing the characteristic polynomial of threshold and chain graphs
- Domination, coloring and stability in \(P_5\)-reducible graphs
- Neighborhood degree lists of graphs
- Many triangles with few edges
- On the complexity of the black-and-white coloring problem on some classes of perfect graphs
- Weak unit disk and interval representation of graphs
- Solving matching problems efficiently in bipartite graphs
- scientific article; zbMATH DE number 5942287 (Why is no real title available?)
- Threshold-coloring and unit-cube contact representation of planar graphs
- H-product of graphs, H-threshold graphs and threshold-width of graphs
- scientific article; zbMATH DE number 1792564 (Why is no real title available?)
- New classes of degree sequences with fast mixing swap Markov chain sampling
- Precoloring Extension III: Classes of Perfect Graphs
- scientific article; zbMATH DE number 1424030 (Why is no real title available?)
- A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs
- Majorization and the number of bipartite graphs for given vertex degrees
- scientific article; zbMATH DE number 3895098 (Why is no real title available?)
- Graphs with the fewest matchings
- Circular-arc bigraphs and its subclasses
- Hereditary efficiently dominatable graphs
- On double bound graphs and forbidden subposets
- Between 2- and 3-colorability
- On double bound graphs and forbidden subposets
- Combinatorics and algorithms for quasi-chain graphs
- On minimal forbidden subgraph characterizations of balanced graphs
- Combinatorics and algorithms for quasi-chain graphs
- Strongly perfect claw‐free graphs—A short proof
- On 4-Sachs optimal graphs
- Certifying fully dynamic algorithms for recognition and Hamiltonicity of threshold and chain graphs
- Verifying the product of generalized Boolean matrix multiplication and its applications to detect small subgraphs
- Graph decompositions in projective geometries
- The chain graph sandwich problem
- A characterization of chain probe graphs
- Two characterizations of chain partitioned probe graphs
- Graphs with minimum degree-entropy
- Extremal values of degree-based entropies of bipartite graphs
- A characterization of claw-free \(b\)-perfect graphs
- Minimal classes of graphs of unbounded clique-width
- Characterization of graphs with the limited normalized algebraic connectivity
- Chain and threshold hypergraphs
- Finding induced subgraphs from graphs with small mim-width
- Some counterexamples to a conjecture on difference graphs
- On bipartite graphs with the minimum number of spanning trees
- Bichain graphs: geometric model and universal graphs
This page was built for publication: Difference graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5895304)
