Threshold Graphs and Related Topics, Volume 56

1st Edition

Authors: N.V.R. Mahadev U.N. Peled
Hardcover ISBN: 9780444892874
eBook ISBN: 9780080543000
Imprint: North Holland
Published Date: 1st September 1995
Page Count: 542
72.95 + applicable tax
43.99 + applicable tax
54.95 + applicable tax
Unavailable
Compatible Not compatible
VitalSource PC, Mac, iPhone & iPad Amazon Kindle eReader
ePub & PDF Apple & PC desktop. Mobile devices (Apple & Android) Amazon Kindle eReader
Mobi Amazon Kindle eReader Anything else

Institutional Access


Table of Contents

Preface. Basic Terminology. 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. Ferrers Digraphs and Difference Graphs. Introduction. Ferrers digraphs, characterizations. The Ferrers dimension. Difference graphs. Degree Sequences. Graphical degree sequences. Threshold sequences. The polytope of degree sequences. Difference sequences. Applications.Introduction. Aggregation of inequalities. Synchronization. Cyclic scheduling. Guttman scales. Split Graphs. Introduction. Basic properties. Hamiltonian split graphs. The splittance of a graph. The Threshold Dimension. Introduction. Bounds for the threshold dimension. Dimensional properties. Operations preserving the threshold dimension. Restricted threshold dimension. NP-Completeness. Introduction. The partial order dimension. Related NP-complete problems. Other complexity results. The split dimension. Polar graphs. 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. The Dilworth Number. Introduction. Graphs of Dilworth number 2. The Dilworth number and perfect graphs. Box-Threshold Graphs. Introduction. Elementary properties. A transportation model. Frames of BT graphs. Matroidal and Matrogenic Graphs. Introduction. Matroidal graphs. Matrogenic graphs. Matrogenic sequences. Domishold Graphs. Introduction. Notation and main results. Equidominating graphs. Pseudodomishold graphs. The Decomposition Method. Introduction. The canonical decomposition. Domishold graphs and decompos

Description

Threshold graphs have a beautiful structure and possess many important mathematical properties. They have applications in many areas including computer science and psychology. Over the last 20 years the interest in threshold graphs has increased significantly, and the subject continues to attract much attention.

The book contains many open problems and research ideas which will appeal to graduate students and researchers interested in graph theory. But above all Threshold Graphs and Related Topics provides a valuable source of information for all those working in this field.


Details

No. of pages:
542
Language:
English
Copyright:
© North Holland 1995
Published:
Imprint:
North Holland
eBook ISBN:
9780080543000
Hardcover ISBN:
9780444892874

Reviews

Threshold graphs have a beautiful structure and possess many important mathematical properties. They have applications in many areas including computer science and psychology. Over the last 20 years the interest in threshold graphs has increased significantly, and the subject continues to attract much attention.

The book contains many open problems and research ideas which will appeal to graduate students and researchers interested in graph theory. But above all Threshold Graphs and Related Topics provides a valuable source of information for all those working in this field.


About the Authors

N.V.R. Mahadev Author

Affiliations and Expertise

Northeastern University, Department of Mathematics, Boston, MA, USA

U.N. Peled Author

Affiliations and Expertise

The University of Illinois at Chicago, Department of Mathematics, Chicago, USA