Topics in Graph Theory: Graphs and Their Cartesian Product

Contents......Page 8
Preface......Page 12
I. Cartesian Products......Page 16
1.1 Definitions, Fibers, and Projections......Page 18
1.2 Connectedness and More Examples......Page 21
1.3 Products of Several Factors......Page 23
1.4 Exercises......Page 24
2.1 Hypercubes and Hamming Graphs......Page 26
2.2 Hanoi Graphs......Page 28
2.3 Exercises......Page 30
II. Classic Topics......Page 32
3.1 Conditions for Hamiltonicity......Page 34
3.2 Hamiltonian Products......Page 35
3.3 Hamiltonian Prisms......Page 40
3.4 Exercises......Page 41
4.1 Planar Products......Page 44
4.2 Crossing Numbers of Products of Cycles......Page 46
4.3 More Exact Crossing Numbers......Page 50
4.4 Exercises......Page 51
5.1 Vertex-Connectivity......Page 52
5.2 Edge-Connectivity......Page 57
5.3 Exercises......Page 59
6.1 Nontrivial Subgraphs......Page 60
6.2 Characterizations......Page 62
6.3 Basic Trivial Subgraphs......Page 64
6.4 Exercises......Page 65
III. Graphical Invariants......Page 68
7.1 Definitions......Page 70
7.2 Lower Bounds......Page 71
7.3 Upper Bounds......Page 74
7.4 Exercises......Page 76
8. Graph Colorings......Page 78
8.1 Vertex Colorings......Page 79
8.2 Generalized Colorings......Page 82
8.3 Circular Colorings......Page 84
8.4 Exercises......Page 86
9.1 List Colorings......Page 88
9.2 L(2, 1)-labelings......Page 90
9.3 Edge Colorings......Page 93
9.4 Exercises......Page 94
10.1 Definitions and Notation......Page 96
10.2 Bounds for γ in Terms of Other Invariants......Page 99
10.3 Exercises......Page 101
11.1 Binary Codes......Page 104
11.2 Multiplicative Results......Page 106
11.3 Lower Bounds......Page 107
11.4 Exercises......Page 110
IV. Metric Aspects......Page 112
12.1 Distance Lemma......Page 114
12.2 Applications of the Distance Lemma......Page 116
12.3 Exercises......Page 118
13.1 Boxes......Page 120
13.2 Metric Boxes......Page 123
13.3 Exercises......Page 126
14.1 Representation α......Page 128
14.2 Properties and Applications of α......Page 132
14.3 Exercises......Page 135
V. Algebraic and Algorithmic Issues......Page 138
15. Prime Factorizations......Page 140
15.1 Uniqueness for Connected Graphs......Page 141
15.2 Automorphisms......Page 143
15.3 Exercises......Page 146
16. Cancelation and Containment......Page 148
16.1 Cancelation Properties......Page 149
16.2 Containment Properties......Page 151
16.3 Exercises......Page 152
17.1 Examples and Products of Two Factors......Page 154
17.2 Cartesian Powers of Graphs......Page 157
17.3 Exercises......Page 160
18.1 The Structure Theorem......Page 162
18.2 A Polynomial Factorization Algorithm......Page 164
18.3 Recognizing Partial Cubes......Page 165
18.4 Exercises......Page 167
Hints and Solutions to Exercises......Page 168
References......Page 206