Examples and Counterexamples in Graph Theory

Cover......Page 1
Title......Page 3
Copyright Page......Page 4
Contents......Page 6
Foreword......Page 8
Preface......Page 10
5. Detours 19......Page 12
3. Line Chromatic Number......Page 23
4. The Total Chromatic Number......Page 24
5. The Achromatic Number......Page 25
2. CONNECTEDNESS......Page 28
3. INDEPENDENCE AND COVERINGS......Page 40
1. Ramsey Numbers......Page 50
2. Generalized Ramsey Numbers......Page 55
3. Other Extremal Problems......Page 58
2. Line Graphs......Page 70
3. Total Graphs......Page 80
4. Entire Graphs......Page 84
5. Sums and Products of Graphs......Page 89
6. Some Handy Tables......Page 97
1. The Automorphism Groups of a Graph......Page 100
2. Symmetry in Graphs......Page 105
3. Graphs with Given Group and Properties......Page 112
2. Planar Graphs......Page 126
3. Outerplanar Graphs......Page 133
4. Non-planar Graphs......Page 135
1. Introduction......Page 146
2. The Original Reconstruction Problem......Page 150
3. Reconstruction from the Set of Non-Isomorphic G_i's......Page 153
4. Reconstruction from the Collection G- {v_i} where v_i is a Pendant Vertex......Page 155
5. The Line Reconstruction Problem......Page 157
6. Reconstruction from N-Point-Deleted Subgraphs, n ? 2......Page 158
7. Reconstruction of Partially Labeled Graphs......Page 159
8. Miscellaneous Questions......Page 161
2. Eulerian Graphs......Page 164
3. Hamiltonian Graphs......Page 166
4. Traversability of Line and Total Graphs......Page 197
2. Sequences......Page 206
3. Girth, Circumference, Diameter, Radius......Page 208
4. Isometric Graphs......Page 209
5. Trees and Cycles......Page 211
6. Matrices......Page 214
7. Intersection Graphs......Page 216
8. The Geometric Dual......Page 220
APPENDIX-The Frucht Notation......Page 222
GLOSSARY......Page 228
LIST OF SYMBOLS......Page 246
REFERENCES......Page 250
INDEX......Page 262