Threshold Graphs and Related Topics (eBook)

Front Cover 1
Threshold Graphs and Related Topics 4
Copyright Page 5
Contents 10
Preface 8
Basic Terminology 16
Chapter 1. Threshold Graphs 22
1.1 Motivation 22
1.2 Basic Characterizations 23
1.3 Minimizing Integral Weights 29
1.4 Perfect Graphs and Algorithms 32
1.5 Threshold and Split Completions 34
1.6 Longest Cycles and Hamiltonicity 37
1.7 Total Coverings and Total Matchings 42
Chapter 2. Ferrers Digraphs and Difference Graphs 48
2.1 Introduction 48
2.2 Ferrers Digraphs, Characterizations 53
2.3 The Ferrers Dimension 61
2.4 Difference Graphs 67
Chapter 3. Degree Sequences 74
3.1 Graphical Degree Sequences 74
3.2 Threshold Sequences 87
3.3 The Polytope of Degree Sequences 90
3.4 Difference Sequences 107
Chapter 4. Applications 112
4.1 Introduction 112
4.2 Aggregation of Inequalities 112
4.3 Synchronization 114
4.4 Cyclic Scheduling 120
4.5 Guttman Scales 124
Chapter 5. Split Graphs 126
5.1 Introduction 126
5.2 Basic Properties 126
5.3 Hamiltonian Split Graphs 131
5.4 The Splittance of a Graph 132
Chapter 6. The Threshold Dimension 138
6.1 Introduction 138
6.2 Bounds for the Threshold Dimension 141
6.3 Dimensional Properties 143
6.4 Operations Preserving the Threshold Dimension 149
6.5 Restricted Threshold Dimension 150
Chapter 7. NP-Completeness 154
7.1 Introduction 154
7.2 The Partial Order Dimension 154
7.3 Related NP-complete Problems 161
7.4 Other Complexity Results 165
7.5 The Split Dimension 178
7.6 Polar Graphs 183
Chapter 8. 2-Threshold Graphs 190
8.1 Introduction 190
8.2 Properties of 2-threshold Graphs 191
8.3 Bithreshold Graphs 194
8.4 Strict 2-Threshold Graphs 201
8.5 Recognizing Threshold Dimension 2 205
8.6 Recognizing Difference Dimension 2 228
8.7 Intersection Threshold Dimension 2 239
Chapter 9. The Dilworth Number 256
9.1 Introduction 256
9.2 Graphs of Dilworth Number 2 260
9.3 The Dilworth Number and Perfect Graphs 267
Chapter 10. Box-Threshold Graphs 272
10.1 Introduction 272
10.2 Elementary Properties 273
10.3 A Transportation Model 277
10.4 Frames of BT Graphs 280
Chapter 11. Matroidal and Matrogenic Graphs 286
11.1 Introduction 286
11.2 Matroidal Graphs 287
11.3 Matrogenic Graphs 311
11.4 Matrogenic Sequences 318
Chapter 12. Domishold Graphs 328
12.1 Introduction 328
12.2 Notation and Main Results 328
12.3 Equidominating Graphs 335
12.4 Pseudodomishold Graphs 338
Chapter 13. The Decomposition Method 342
13.1 Introduction 342
13.2 The Canonical Decomposition 343
13.3 Domishold Graphs and Decomposition 350
13.4 Box-Threshold Graphs and Decomposition 356
13.5 Matroidal and Matrogenic Graphs and Decomposition 363
Chapter 14. Pseudothreshold and Equistable Graphs 366
14.1 Introduction 366
14.2 Pseudothreshold Graphs 366
14.3 Equistable Graphs 371
Chapter 15. Threshold Weights and Measures 390
15.1 Introduction 390
15.2 Threshold Weights 391
15.3 Threshold Measures 401
15.4 Threshold and Majorization Gaps 416
Chapter 16. Threshold Graphs and Order Relations 450
16.1 Introduction 450
16.2 Biorders 452
16.3 Bidimensions 459
16.4 Relations of Bidimension 2 470
16.5 Multiple Semiorders 475
Chapter 17. Enumeration 482
17.1 Introduction 482
17.2 Enumeration of Threshold Graphs 483
17.3 Enumeration of Difference Graphs 492
Chapter 18. Extremal Problems 498
18.1 Introduction 498
18.2 Large Interval and Threshold Subgraphs of Dense Graphs 499
18.3 Maximizing the Sum of Squares of Degrees 503
Chapter 19. Other Extensions 512
19.1 Introduction 512
19.2 Geometric Embeddings of Graphs 513
19.3 Tolerance Intersection Graphs 520
19.4 Universal Threshold Graphs 524
Bibliography 528
List of Notations 543
Author Index 545
Index 548