简介
Summary:
Publisher Summary 1
This book serves as an introduction to advanced applications of graph theory and provides a survey of recent developments in the field by looking in particular at Cartesian products鈥攁rguably the most important of the four standard graph products. Some of the material is published here for the first time. Its accessible style makes it suitable as a text in modern graph theory as well as for personal study.
Publisher Summary 2
Graphs are as commonplace now in the biological and social sciences as in computer science and engineering. For students who have taken introductory courses in graph theory and algebra, Imrich (Montanuniversit盲t Leoben, Austria) and other experts in the field introduce the Cartesian product (the product set containing all possible combinations of one element from each set). The idea can be extended to products of any number of sets. As represented in the major classes of Tower of Hanoi and Hamming hypercube graphs; its classic topics: e.g., hamiltoniciy, planarity, connectivity, and subgraphs; and examples of diverse applications. Chapters include theorem derivations with some new results, diagrams, and exercises. Indexed by symbol and subject. Annotation 漏2009 Book News, Inc., Portland, OR (booknews.com)
Publisher Summary 3
This book serves as an introduction to advanced applications of graph theory and provides a survey of recent developments in the field by looking in particular at Cartesian products鈥攁rguably the most important of the four standard graph products.
目录
Contents
Preface iii
I CARTESIAN PRODUCTS 1
1 The Cartesian Product 3
1.1 Definition, Fibers and Projections . . . . . . . . . . . . . . . 3
1.2 Connectedness and More Examples . . . . . . . . . . . . . . . 6
1.3 Products of Several Factors . . . . . . . . . . . . . . . . . . . 8
1.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2 Hamming Graphs and Hanoi Graphs 11
2.1 Hypercubes and Hamming Graphs . . . . . . . . . . . . . . . 11
2.2 Hanoi Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
II CLASSICAL TOPICS 17
3 Hamiltonian Graphs 19
3.1 Conditions for Hamiltonicity . . . . . . . . . . . . . . . . . . 19
3.2 Hamiltonian Products . . . . . . . . . . . . . . . . . . . . . . 20
3.3 Hamiltonian Prisms . . . . . . . . . . . . . . . . . . . . . . . 24
3.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4 Planarity and Crossing Number 29
4.1 Planar Products . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.2 Crossing Numbers of Products of Cycles . . . . . . . . . . . . 31
4.3 More Exact Crossing Numbers . . . . . . . . . . . . . . . . . 34
4.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
vii
viii CONTENTS
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
5 Connectivity 39
5.1 Vertex-Connectivity . . . . . . . . . . . . . . . . . . . . . . . 39
5.2 Edge-Connectivity . . . . . . . . . . . . . . . . . . . . . . . . 43
5.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
6 Subgraphs 47
6.1 Nontrivial Subgraphs . . . . . . . . . . . . . . . . . . . . . . . 47
6.2 Characterizations . . . . . . . . . . . . . . . . . . . . . . . . . 48
6.3 Basic Trivial Subgraphs . . . . . . . . . . . . . . . . . . . . . 51
6.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
III GRAPHICAL INVARIANTS 55
7 Independence 57
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
7.2 Lower Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
7.3 Upper Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . 61
7.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
8 Graph Colorings 65
8.1 Vertex Colorings . . . . . . . . . . . . . . . . . . . . . . . . . 65
8.2 Generalized Colorings . . . . . . . . . . . . . . . . . . . . . . 68
8.3 Circular Colorings . . . . . . . . . . . . . . . . . . . . . . . . 70
8.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
9 Additional Types of Colorings 75
9.1 List Colorings . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
9.2 L(2, 1)-labellings . . . . . . . . . . . . . . . . . . . . . . . . . 77
9.3 Edge Colorings . . . . . . . . . . . . . . . . . . . . . . . . . . 79
9.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
10 Domination 83
10.1 Definitions and Notation . . . . . . . . . . . . . . . . . . . . . 83
10.2 Bounds for ? in Terms of Other Invariants . . . . . . . . . . . 86
10.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
CONTENTS ix
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
11 Domination in Cartesian Products 91
11.1 Binary Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
11.2 Multiplicative Results . . . . . . . . . . . . . . . . . . . . . . 92
11.3 Lower Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
11.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
IV METRIC ASPECTS 101
12 Distance Lemma and Wiener Index 103
12.1 Distance Lemma . . . . . . . . . . . . . . . . . . . . . . . . . 103
12.2 Applications of the Distance Lemma . . . . . . . . . . . . . . 105
12.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
13 Products and Boxes 109
13.1 Boxes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
13.2 Metric Boxes . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
13.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
14 Canonical Metric Representation 117
14.1 Representation a . . . . . . . . . . . . . . . . . . . . . . . . . 117
14.2 Properties and Applications of a . . . . . . . . . . . . . . . . 121
14.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
V ALGEBRAIC AND ALGORITHMIC ISSUES 127
15 Prime Factorizations 129
15.1 Uniqueness for Connected Graphs . . . . . . . . . . . . . . . 130
15.2 Automorphisms . . . . . . . . . . . . . . . . . . . . . . . . . . 131
15.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
16 Cancelation and Containment 137
16.1 Cancelation Properties . . . . . . . . . . . . . . . . . . . . . . 138
16.2 Containment Properties . . . . . . . . . . . . . . . . . . . . . 140
16.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
x CONTENTS
17 Distinguishing Number 143
17.1 Examples and Products of Two Factors . . . . . . . . . . . . 143
17.2 Cartesian Powers of Graphs . . . . . . . . . . . . . . . . . . . 146
17.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
18 Recognizing Products 151
18.1 The Structure Theorem . . . . . . . . . . . . . . . . . . . . . 151
18.2 A Polynomial Factorization Algorithm . . . . . . . . . . . . . 153
18.3 Partial Cubes . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
18.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
VI ANSWERS TO THE EXERCISES 159
19 Hints and Solutions to Exercises 161
19.1 Part I - Cartesian Products . . . . . . . . . . . . . . . . . . . 161
19.2 Part II - Classical Topics . . . . . . . . . . . . . . . . . . . . . 164
19.3 Part III - Graphical Invariants . . . . . . . . . . . . . . . . . 171
19.4 Part IV - Metric Aspects . . . . . . . . . . . . . . . . . . . . . 179
19.5 Part V - Algebraic and Algorithmic Issues . . . . . . . . . . . 184
Name Index 195
Symbol Index 197
Subject Index 198
- 名称
- 类型
- 大小
光盘服务联系方式: 020-38250260 客服QQ：4006604884
云图客服：
用户发送的提问，这种方式就需要有位在线客服来回答用户的问题，这种 就属于对话式的,问题是这种提问是否需要用户登录才能提问
Video Player
×
Audio Player
×
pdf Player
×
