To order this title, and for more information, click here
By N.V.R. Mahadev, Northeastern University, Department of Mathematics, Boston, MA, USA U.N. Peled, The University of Illinois at Chicago, Department of Mathematics, Chicago, USA
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.
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.
Domishold Graphs. Introduction. Notation and
main results. Equidominating graphs. Pseudodomishold graphs.
The Decomposition Method. Introduction. The canonical decomposition.
Domishold graphs and decomposition. Box-threshold graphs and decomposition. Matroidal and matrogenic graphs and decomposition.
Pseudothreshold
and Equistable Graphs. Introduction. Pseudothreshold graphs. Equistable graphs.
Threshold Weights and Measures. Introduction.
Threshold weights. Threshold measures. Threshold and majorization gaps.
Threshold Graphs and Order Relations. Introduction.
Biorders. Bidimensions. Relations of bidimension 2. Multiple semiorders.
Enumeration. Introduction. Enumeration of threshold
graphs. Enumeration of difference graphs.
Extremal Problems. Introduction. Large interval and threshold subgraphs of
dense graphs. Maximizing the sum of squares of degrees.
Other Extensions. Introduction. Geometric embeddings of graphs.
Tolerance intersection graphs. Universal threshold graphs.
Bibliography. List of Notations. Author Index. Index.
Books and book related electronic products are priced in US dollars (USD), euro (EUR), and Great Britain Pounds (GBP). USD prices apply to the Americas and Asia Pacific. EUR prices apply in Europe and the Middle East. GBP prices apply to the UK and all other countries.
Home | Elsevier Sites | Privacy Policy | Terms and Conditions | Feedback | Site Map | A Reed Elsevier Company