Matrices in Combinatorics and Graph Theory
Combinatorics and Matrix Theory have a symbiotic, or mutually beneficial, relationship. This relationship is discussed in my paper The symbiotic relationship of combinatorics and matrix theoryl where I attempted to justify this description. One could say
- PDF / 24,745,755 Bytes
- 317 Pages / 439.37 x 666.142 pts Page_size
- 27 Downloads / 276 Views
Network Theory and Applications Volume 3
Matrices in Combinatorics and Graph Theory by
Bolian Liu Department of Mathematics, South China Normal University, Guangzhou, P. R. China and
Hong-Jian Lai Department of Mathematics, West Virginia University, Morgantown, West Virginia, U.S.A .
SPRINGER-SCIENCE+BUSINESS MEDIA, B.V.
A C.I.P. Catalogue record for this book is available from the Library of Congress.
ISBN 978-1-4419-4834-2 ISBN 978-1-4757-3165-1 (eBook) DOI 10.1007/978-1-4757-3165-1
Printed on acid-free paper
All Rights Reserved © 2000 Springer Science+Business Media Dordrecht Originally published by Kluwer Academic Publishers in 2000 Softcover reprint of the hardcover 1st edition 2000
No part of the material protected by this copyright notice may be reproduced or utilized in any form or by any means, electronic or mechanical, including photocopying, recording or by any information storage and retrieval system, without written permission from the copyright owner.
Contents Foreword
ix
Preface
xi
1
Matrices and Graphs 1.1
1.2 1.3 1.4 1.5 1.6 1.7 1.8 2
Estimating the Eigenvalues of a Graph . Line Graphs and Total Graphs Cospectral Graphs Spectral Radius . . Exercises Hints for Exercises
Combinatorial Properties of Matrices
2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 2.10 3
The Basics The Spectrum of a Graph
Irreducible and Fully Indecomposable Matrices Standard Forms. . . . . . . Nearly Reducible Matrices. Nearly Decomposable Matrices Permanent . . . . The Class U(r, s) Stochastic Matrices and Doubly Stochastic Matrices Birkhoff Type Theorems Exercise . . . . . . Hints for Exercises
Powers of Nonnegative Matrices
3.1 The Frobenius Diophantine Problem ...... 3.2 The Period and The Index of a Boolean Matrix
1
1 5 12 17 20 24 38 41 47 48 50 54 58 61 71 77 81 90 92 97 97 101
Contents
vi 3.3 3.4 3.5 3.6 3.7 3.8 3.9
The Primitive Exponent . . . . . . . . . . . . . . . . . . . . . . The Index of Convergence of Irreducible Nonprimitive Matrices The Index of Convergence of Reducible Nonprimitive Matrices Index of Density . . . . . . . . . . . . . . . . . . . . Generalized Exponents of Primitive Matrices . . . . Fully indecomposable exponents and Hall exponents Primitive exponent and other parameters
.107 · 114 · 120 · 125 · 129 · 136 · 146
3.10 Exercises . . . . . 3.11 Hint for Exercises . . . . . . . . . . .
· 150 · 153
4 Matrices in Combinatorial Problems
161
4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 4.10 5
6
Matrix Solutions for Difference Equations Matrices in Some Combinatorial Configurations. Decomposition of Graphs Matrix-Thee Theorems . . Shannon Capacity . . . . Strongly Regular Graphs. Eulerian Problems . . . The Chromatic Number Exercises . . . . . Hints for Exercises . . .
· 161 · 166 · 171 · 176 · 180 .190 · 196 .204 · 210 · 212
217
Combinatorial Analysis in Matrices 5.1 Combinatorial Representation of Matrices and Determinants 5.2 Combinatorial Proofs in Linear Algebra . 5.3 Generalized Inverse of a Boolean Matrix . 5.4 Maximum Determinant of a (0,1) Matrix. 5.5 Rearrangement of (0
