Details

Autor(en) / Beteiligte

• Thulasiraman, K
• Swamy, M. N. S

Titel

Graphs : theory and algorithms

Beschreibungen/Notizen

• "A Wiley-Interscience publication."
• Includes bibliographical references and indexes.
• Graphs: Theory and Algorithms; Contents; PREFACE; 1 BASIC CONCEPTS; 1.1 Some Basic Definitions; 1.2 Subgraphs and Complements; 1.3 Walks, Trails, Paths, and Circuits; 1.4 Connectedness and Components of a Graph; 1.5 Operations on Graphs; 1.6 Special Graphs; 1.7 Cut-Vertices and Separable Graphs; 1.8 Isomorphism and 2-Isomorphism; 1.9 Further Reading; 1.10 Exercises; 1.11 References; 2 TREES, CUTSETS, AND CIRCUITS; 2.1 Trees, Spanning Trees, and Cospanning Trees; 2.2 k-Trees, Spanning k-Trees, and Forests; 2.3 Rank and Nullity; 2.4 Fundamental Circuits; 2.5 Cutsets; 2.6 Cuts
• 2.7 Fundamental Cutsets2.8 Spanning Trees, Circuits, and Cutsets; 2.9 Further Reading; 2.10 Exercises; 2.11 References; 3 EULERIAN AND HAMILTONIAN GRAPHS; 3.1 Eulerian Graphs; 3.2 Hamiltonian Graphs; 3.3 Further Reading; 3.4 Exercises; 3.5 References; 4 GRAPHS AND VECTOR SPACES; 4.1 Groups and Fields; 4.2 Vector Spaces; 4.3 Vector Space of a Graph; 4.4 Dimensions of Circuit and Cutset Subspaces; 4.5 Relationship between Circuit and Cutset Subspaces; 4.6 Orthogonality of Circuit and Cutset Subspaces; 4.7 Further Reading; 4.8 Exercises; 4.9 References; 5 DIRECTED GRAPHS
• 5.1 Basic Definitions and Concepts5.2 Graphs and Relations; 5.3 Directed Trees or Arborescences; 5.4 Directed Eulerian Graphs; 5.5 Directed Spanning Trees and Directed Euler Trails; 5.6 Directed Hamiltonian Graphs; 5.7 Acyclic Directed Graphs; 5.8 Tournaments; 5.9 Further Reading; 5.10 Exercises; 5.11 References; 6 MATRICES OF A GRAPH; 6.1 Incidence Matrix; 6.2 Cut Matrix; 6.3 Circuit Matrix; 6.4 Orthogonality Relation; 6.5 Submatrices of Cut, Incidence, and Circuit Matrices; 6.6 Unimodular Matrices; 6.7 The Number of Spanning Trees; 6.8 The Number of Spanning 2-Trees
• 6.9 The Number of Directed Spanning Trees in a Directed Graph6.10 Adjacency Matrix; 6.11 The Coates and Mason Graphs; 6.12 Further Reading; 6.13 Exercises; 6.14 References; 7 PLANARITY AND DUALITY; 7.1 Planar Graphs; 7.2 Euler's Formula; 7.3 Kuratowski's Theorem and Other Characterizations of Planarity; 7.4 Dual Graphs; 7.5 Planarity and Duality; 7.6 Further Reading; 7.7 Exercises; 7.8 References; 8 CONNECTIVITY AND MATCHING; 8.1 Connectivity or Vertex Connectivity; 8.2 Edge Connectivity; 8.3 Graphs with Prescribed Degrees; 8.4 Menger's Theorem; 8.5 Matchings
• 8.6 Matchings in Bipartite Graphs8.7 Matchings in General Graphs; 8.8 Further Reading; 8.9 Exercises; 8.10 References; 9 COVERING AND COLORING; 9.1 Independent Sets and Vertex Covers; 9.2 Edge Covers; 9.3 Edge Coloring and Chromatic Index; 9.4 Vertex Coloring and Chromatic Number; 9.5 Chromatic Polynomials; 9.6 The Four-Color Problem; 9.7 Further Reading; 9.8 Exercises; 9.9 References; 10 MATROIDS; 10.1 Basic Definitions; 10.2 Fundamental Properties; 10.3 Equivalent Axiom Systems; 10.4 Matroid Duality and Graphoids; 10.5 Restriction, Contraction, and Minors of a Matroid
• 10.6 Representability of a Matroid
• This adaptation of an earlier work by the authors is a graduate text and professional reference on the fundamentals of graph theory. It covers the theory of graphs, its applications to computer networks and the theory of graph algorithms. Also includes exercises and an updated bibliography.
• English