Graphical Enumeration (eBook)

Frank Harary, Edgar M. Palmer (Autoren)

eBook Download: PDF

2014 | 1. Auflage
286 Seiten
Elsevier Science (Verlag)
978-1-4832-7378-5 (ISBN)

Infos

Graphical Enumeration deals with the enumeration of various kinds of graphs. Topics covered range from labeled enumeration and George Pólya's theorem to rooted and unrooted trees, graphs and digraphs, and power group enumeration. Superposition, blocks, and asymptotics are also discussed. A number of unsolved enumeration problems are presented. Comprised of 10 chapters, this book begins with an overview of labeled graphs, followed by a description of the basic enumeration theorem of Pólya. The next three chapters count an enormous variety of trees, graphs, and digraphs. The Power Group Enumeration Theorem is then described together with some of its applications, including the enumeration of self-complementary graphs and digraphs and finite automata. Two other chapters focus on the counting of superposition and blocks, while another chapter is devoted to asymptotic numbers that are developed for several different graphical structures. The book concludes with a comprehensive definitive list of unsolved graphical enumeration problems. This monograph will be of interest to both students and practitioners of mathematics.

---

Graphical Enumeration deals with the enumeration of various kinds of graphs. Topics covered range from labeled enumeration and George Polya's theorem to rooted and unrooted trees, graphs and digraphs, and power group enumeration. Superposition, blocks, and asymptotics are also discussed. A number of unsolved enumeration problems are presented. Comprised of 10 chapters, this book begins with an overview of labeled graphs, followed by a description of the basic enumeration theorem of Polya. The next three chapters count an enormous variety of trees, graphs, and digraphs. The Power Group Enumeration Theorem is then described together with some of its applications, including the enumeration of self-complementary graphs and digraphs and finite automata. Two other chapters focus on the counting of superposition and blocks, while another chapter is devoted to asymptotic numbers that are developed for several different graphical structures. The book concludes with a comprehensive definitive list of unsolved graphical enumeration problems. This monograph will be of interest to both students and practitioners of mathematics.

Inhalt

Front Cover 1
Graphical Enumeration 4
Copyright Page 5
Table of Contents 8
Dedication 6
Preface 12
CHAPTER 1. LABELED ENUMERATION 16
1.1 The Number of Ways to Label a Graph 17
1.2 Connected Graphs 21
1.3 Blocks 24
1.4 Eulerian Graphs 26
1.5 The Number of k-Colored Graphs 31
1.6 Acyclic Digraphs 33
1.7 Trees 35
1.8 Eulerian Trails in Digraphs 40
Exercises 44
CHAPTER 2. POLYA'S THEOREM 47
2.1 Groups and Graphs 48
2.2 The Cycle Index of a Permutation Group 50
2.3 Burnside's Lemma 53
2.4 Polya's Theorem 56
2.5 The Special Figure Series 1 + x 61
2.6 One-One Functions 62
Exercises 64
CHAPTER 3. TREES 66
3.1 Rooted Trees 66
3.2 Unrooted Trees 70
3.3 Trees with Specified Properties 74
3.4 Treelike Graphs 83
3.5 Two-Trees 88
Exercises 94
CHAPTER 4. GRAPHS 96
4.1 Graphs 97
4.2 Connected Graphs 105
4.3 Bicolored Graphs 108
4.4 Rooted Graphs 115
4.5 Supergraphs and Colored Graphs 119
4.6 Boolean Functions 124
4.7 Eulerian Graphs 128
Exercises 132
CHAPTER 5. DIGRAPHS 134
5.1 Digraphs 135
5.2 Tournaments 139
5.3 Orientations of a Graph 142
5.4 Mixed Graphs 144
Exercises 148
CHAPTER 6. POWER GROUP ENUMERATION 150
6.1 Power Group Enumeration Theorem 151
6.2 Self-Complementary Graphs 153
6.3 Functions with Weights 156
6.4 Graphs with Colored Lines 159
6.5 Finite Automata 161
6.6 Self-Converse Digraphs 165
Exercises 170
CHAPTER 7. SUPERPOSITION 173
7.1 Redfield's Enumeration Theorem 174
7.2 Redfield's Decomposition Theorem 177
7.3 Graphs and Digraphs 182
7.4 A Generalization of Redfield's Enumeration Theorem 183
7.5 General Graphs 187
Exercises 191
CHAPTER 8. BLOCKS 192
8.1 A Generalization of Redfield's Lemma 193
8.2 The Composition Group 193
8.3 The Composition Theorem 196
8.4 Connected Graphs 197
8.5 Cycle Index Sums for Rooted Graphs 199
8.6 Blocks 200
8.7 Graphs with Given Blocks 203
8.8 Acyclic Digraphs 206
Exercises 209
CHAPTER 9. ASYMPTOTICS 210
9.1 Graphs 211
9.2 Digraphs 214
9.3 Graphs with a Given Number of Points and Lines 216
9.4 Connected Graphs and Blocks 220
9.5 Trees 223
Exercises 229
CHAPTER 10. UNSOLVED PROBLEMS 231
10.1 Labeled Graphs 232
10.2 Digraphs 232
10.3 Graphs with Given Structural Properties 234
10.4 Graphs with Given Parameter 237
10.5 Subgraphs of a Given Graph 241
10.6 Supergraphs of a Given Graph 242
10.7 Graphs and Coloring 243
10.8 Variations on Graphs 245
APPENDIXES I 254
APPENDIXES II 262
APPENDIXES III 264
BIBLIOGRAPHY 268
Index 278

Produkt-Details

• Erscheint lt. Verlag: 10.5.2014
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Mathematik
• Themenwelt: Technik
• ISBN-10: 1-4832-7378-4 / 1483273784
• ISBN-13: 978-1-4832-7378-5 / 9781483273785