Introduction to Graph TheoryThe main objective of this work is to develop a thorough understanding of the structure of graphs and the techniques used to analyze problems in graph theory. Fundamental graph algorithms are also included. Examples and over 600 exercises - at various levels of difficulty - guide students. |
Contents
Fundamental Concepts | 1 |
Trees and Distance | 51 |
Spanning Trees in Graphs | 65 |
Copyright | |
14 other sections not shown
Other editions - View all
Common terms and phrases
2-connected 3-regular adjacency matrix algorithm bipartite graph chordal graph chromatic number circuit components compute condition connected graph construct contains cycle matroid deleting digraph disjoint dual edge-disjoint edges incident edges of G eigenvalues embedding endpoints Eulerian Eulerian circuit Example Exercise function G₁ graph G Hamiltonian cycle Hamiltonian path Hence hereditary system Hint implies independent set induced subgraph inequality integer intersection interval graphs isolated vertices isomorphic k-coloring k-critical labeling Lemma lower bound matching matroid maximal maximum clique minimal minimum number n-vertex graph NP-complete number of edges number of vertices obtain odd cycle pair pairwise path perfect graphs Petersen graph planar graph plane polynomial problem Proof Prove that G random graphs regular graphs satisfies sequence simple graph simplicial spanning cycle spanning tree stable set subgraph of G subsets Suppose G Theorem tion triangle v₁ vectors vertex degrees vertex set y-path yields