Spanning Tree Results For Graphs And Multigraphs: A Matrix-theoretic Approach

by John T Saccoman, Daniel J Gross, Charles L Suffel

Overview

This book is concerned with the optimization problem of maximizing the number of spanning trees of a multigraph. Since a spanning tree is a minimally connected subgraph, graphs and multigraphs having more of these are, in some sense, immune to disconnection by edge failure. We employ a matrix-theoretic approach to the calculation of the number of spanning trees.The authors envision this as a research aid that is of particular interest to graduate students or advanced undergraduate students and researchers in the area of network reliability theory. This would encompass graph theorists of all stripes, including mathematicians, computer scientists, electrical and computer engineers, and operations researchers.

Product Details

ISBN-13:	9789814566032
Publisher:	World Scientific Publishing Company, Incorporated
Publication date:	10/23/2014
Pages:	188
Product dimensions:	6.10(w) x 9.10(h) x 0.70(d)

Table of Contents

Preface vii

0 An Introduction to Relevant Graph Theory and Matrix Theory 1

0.1 Graph Theory 1

0.2 Matrix Theory 19

1 Calculating the Number of Spanning Trees: The Algebraic Approach 37

1.1 The Node-Arc Incidence Matrix 38

1.2 Laplacian Matrix 41

1.3 Special Graphs 50

1.4 Temperley's B-Matrix 72

1.5 Multigraphs 77

1.6 Eigenvalue Bounds for Multigraphs 79

1.7 Multigraph Complements 84

1.8 Two Maximum Tree Results 89

2 Multigraphs with the Maximum Number of Spanning Trees: An Analytic Approach 93

2.1 The Maximum Spanning Tree Problem 93

2.2 Two Maximum Spanning Tree Results 105

3 Threshold Graphs 111

3.1 Characteristic Polynomials of Threshold Graphs 111

3.2 Minimum Number of Spanning Trees 123

4 Approaches to the Multigraph Problem 147

5 Laplacian Integral Graphs and Multigraphs 159

5.1 Complete Graphs and Related Structures 159

5.2 Split Graphs and Related Structures 161

5.3 Laplacian Integral Multigraphs 165

Bibliography 169

Index 173