TY  - BOOK
AU  - Mahedev, N.V.R.
AU  - Peled, U.N.
TI  - Threshold graphs and related topics
T2  - Annals of Discrete Mathematics, Vol 56
SN  - 0444892877
PY  - 1995///
CY  - Netherlands
PB  - North-Holland
KW  - COMPUTING
KW  - GRAPHS
N1  - ICT; An introduction to threshold graphs which have many applications in areas including computer science and psychology. This text contains many open problems and research ideas which should appeal to graduate students and researchers interested in graph theory; Part 1 Threshold graphs: motivation; basic characterizations; minimizing integral weights; perfect graphs and algorithms; threshold and split completions; longest cycles and Hamiltonicity; total coverings and total matchings. Part 2 Ferrers digraphs and difference graphs: introduction; Ferrers digraphs, characterizations; the Ferrers dimension; difference graphs. Part 3 Degree sequences: graphical degree sequences; threshold sequences; the polytope of degree sequences; difference sequences. Part 4 Applications: introduction; aggregation of inequalities; synchronization; cyclic scheduling; Guttman scales. Part 5 Split graphs: introduction; basic properties; Hamiltonian split graphs; the splittance of a graph. Part 6 The threshold dimension: introduction; bounds for the threshold dimension; dimensional properties; operations preserving the threshold dimension; restricted threshold dimension. Part 7 NP-completeness: introduction; the partial order dimension; related NP-complete problems; other complexity results; the split dimension; polar graphs. Part 8 2-Threshold graphs: introduction; properties of 2-threshold graphs; bithreshold graphs; strict 2-threshold graphs; recognizing threshold dimension 2; recognizing difference dimension 2; intersection threshold dimension 2. Part 9 The Dilworth number: introduction; graphs of Dilworth number 2; the Dilworth number of perfect graphs. Part 10 Box-threshold graphs: introduction; elementary properties; a transportation model; frames of BT graphs. Part 11 Matroidal and matrogenic graphs: introduction; matroidal graphs; matrogenic graphs; matrogenic sequences. Part 12 Domishold graphs: introduction; notation and main results; equidominatng graphs; pseudodomishold graphs. Part 13 The decomposition method: introduction; the canonical decomposition; domishold graphs and decomposition; box-threshold graphs and decomposition; matroidal and matrogenic graphs and decomposition. Part 14 Pseudothreshold and equistable graphs: introduction; pseudothreshold graphs; equistable graphs. Part 15 Threshold weights and measures: introduction; threshold weights; threshold measures; threshold and majorization gaps. Part 16 Threshold graphs and order relations: introduction; biorders; bidimensions; relations of bidimension 2; multiple semiorders. Part 17 Enumeration: introduction; enumeration of threshold graphs; enumeration of difference graphs. Part 18 Extremal problems: introduction; large interval and threshold subgraphs of dense graphs; maximizing the sum of squares of degrees. Part 19 Other extensions: introduction; geometric embeddings of graphs; tolerance intersection graphs; universal threshold graphs
ER  -