Topics in structural graph theory (Cambridge; New York, 2013). - ОГЛАВЛЕНИЕ / CONTENTS
Навигация

Архив выставки новых поступлений | Отечественные поступления | Иностранные поступления | Сиглы
ОбложкаTopics in structural graph theory / ed. by L.W.Beineke, R.J.Wilson; acad. cons. O.R.Oellermann. - Cambridge; New York: Cambridge univ. press, 2013. - xii, 327 p.: ill. - (Encyclopedia of mathematics and its applications; 147). - Incl. bibl. ref. - Ind.: p.323-327. - Пер. загл.: Некоторые предметы обсуждения в структурной теории графов. - ISBN 978-0-521-80231-4
 

Место хранения: 02 | Отделение ГПНТБ СО РАН | Новосибирск

Оглавление / Contents
 
Foreword by Ortrud R. Oellermann ............................... xi
Preface ...................................................... xiii

   Preliminaries ................................................ 1
   LOWELL W. BEINEKE and ROBIN J. WILSON
   1  Graph theory .............................................. 1
   2  Connectivity .............................................. 8
   3  Flows in networks ........................................ 10

1  Menger's theorem ............................................ 13
   ORTRUD R. OELLERMANN
   1  Introduction ............................................. 13
   2  Vertex-connectivity ...................................... 14
   3  Edge-connectivity ........................................ 18
   4  Mixed connectivity ....................................... 19
   5  Average connectivity ..................................... 22
   6  Menger results for paths of bounded length ............... 28
   7  Connectivity of sets ..................................... 30
   8  Connecting with trees .................................... 32

2  Maximally connected graphs .................................. 40
   DIRK MEIERLING and LUTZ VOLKMANN
   1  Introduction ............................................. 40
   2  Maximally edge-connected graphs .......................... 41
   3  Maximally edge-connected digraphs ........................ 46
   4  Maximally locally edge-connected graphs and digraphs ..... 48
   5  Maximally connected and maximally locally connected
      graphs and digraphs ...................................... 50
   6  Restricted edge-connectivity ............................. 54
   7  Conditional vertex-connectivity and edge-connectivity .... 58

3  Minimal connectivity ........................................ 71
   MATTHIAS KRIESELL
   1  Introduction ............................................. 71
   2  Edge-deletion ............................................ 73
   3  Vertex-deletion .......................................... 74
   4  Edge-contraction ......................................... 79
   5  Generalized criticality .................................. 81
   6  Reduction methods ........................................ 82
   7  Subgraph-deletion ........................................ 88
   8  Partitions under connectivity constraints ................ 91
   9  Line graphs .............................................. 94

4  Contractions of k-connected graphs ......................... 100
   KIYOSHI ANDO
   1  Introduction ............................................ 100
   2  Contractible edges in 3-connected graphs ................ 101
   3  Contractible edges in 4-connected graphs ................ 102
   4  Contractible edges in k-connected graphs ................ 103
   5  Contraction-critical 5-connected graphs ................. 106
   6  Local structure and contractible edges .................. 109
   7  Concluding remarks ...................................... 111

5  Connectivity and cycles .................................... 114
   R.J. FAUDREE
   1  Introduction ............................................ 114
   2  Generalizations of classical results .................... 115
   3  Relative lengths of paths and cycles .................... 117
   4  Regular graphs .......................................... 119
   5  Bipartite graphs ........................................ 122
   6  Claw-free graphs ........................................ 123
   7  Planar graphs ........................................... 128
   8  The Chvátal-Erdos condition ............................. 131
   9  Ordered graphs .......................................... 132
   10 Numbers of cycles ....................................... 134

6  H-linked graphs ............................................ 141
   MICHAEL FERRARA and RONALD J. GOULD
   1  Introduction ............................................ 141
   2  fc-linked graphs ........................................ 143
   3  Weak linkage ............................................ 149
   4  Digraphs ................................................ 150
   5  Modulo and parity linkage ............................... 152
   6  Disjoint connected subgraphs ............................ 154
   7  The disjoint paths problem .............................. 154
   8  H-linked graphs ......................................... 155
   9  H-extendible graphs ..................................... 159

7  Tree-width and graph minors ................................ 165
   DIETER RAUTENBACH and BRUCE REED
   1  Introduction ............................................ 165
   2  Subtree intersection representation ..................... 166
   3  Tree decomposition and tree-width ....................... 168
   4  Tree decompositions decompose ........................... 173
   5  Excluding planar minors ................................. 174
   6  Wagner's conjecture ..................................... 175
   7  The dual of tree-width .................................. 176
   8  A canonical tree decomposition .......................... 178
   9  Wagner's conjecture for arbitrary graphs ................ 180
   10 Efficient characterization of H-minor-free graphs ....... 181

8  Toughness and binding numbers .............................. 185
   IAN ANDERSON
   1  Introduction ............................................ 185
   2  Toughness and connectivity .............................. 187
   3  Toughness and cycles .................................... 188
   4  Toughness and k-factors ................................. 191
   5  Binding number .......................................... 194
   6  Binding number and k-factors ............................ 196
   7  Binding numbers and cycles .............................. 198
   8  Other measures of vulnerability ......................... 198

9  Graph fragmentability ...................................... 203
   KEITH EDWARDS and GRAHAM FARR
   1  Introduction ............................................ 203
   2  Values and bounds for fragmentability ................... 206
   3  Reduction and separation ................................ 207
   4  Bounded degree classes .................................. 208
   5  Planarization ........................................... 210
   6  Applications ............................................ 214
   7  Monochromatic components ................................ 215
   8  Open problems ........................................... 216

10 The phase transition in random graphs ...................... 219
   BÉLA BOLLOBÁS and OLIVER RIORDAN
   1. Introduction ............................................ 219
   2  The Erdős-Rényi theorem: the double jump ................ 223
   3  Correction: no double jump .............................. 225
   4  The phase transition - simple results ................... 227
   5  Exploring components .................................... 238
   6  The phase transition - finer results .................... 240
   7  The young giant ......................................... 243
   8  Final words ............................................. 247

11 Network reliability and synthesis .......................... 251
   F.T. BOESCH, A. SATYANARAYANA and C.L. SUFFEL
   1  Introduction ............................................ 251
   2  Domination in digraphs .................................. 252
   3  Coherent systems and domination in graphs ............... 255
   4  Computational complexity of reliability ................. 260
   5  Synthesis of reliable networks .......................... 260
   6  Other measures of vulnerability ......................... 263

12 Connectivity algorithms .................................... 268
   ABDOL-HOSSEIN ESFAHANIAN
   1  Introduction ............................................ 268
   2  Computing the edge-connectivity ......................... 269
   3  Computing the arc-connectivity .......................... 274
   4  Computing the vertex-connectivity ....................... 275
   5  Concluding remarks ...................................... 279

13 Using graphs to find the best block designs ................ 282
   R.A. BAILEY and PETER J. CAMERON
   1  What makes a block design good? ......................... 283
   2  Graphs from block designs ............................... 284
   3  Statistical issues ...................................... 288
   4  Highly patterned block designs .......................... 292
   5  D-optimality ............................................ 293
   6  A-optimality ............................................ 294
   7  E-optimality ............................................ 302
   8  Some history ............................................ 304
   9  Block size 2 ............................................ 306
   10 Low average replication ................................. 311
   11 Further reading ......................................... 314

Notes on contributors ......................................... 318

Index ......................................................... 323


Архив выставки новых поступлений | Отечественные поступления | Иностранные поступления | Сиглы
 

[О библиотеке | Академгородок | Новости | Выставки | Ресурсы | Библиография | Партнеры | ИнфоЛоция | Поиск]
  Пожелания и письма: branch@gpntbsib.ru
© 1997-2024 Отделение ГПНТБ СО РАН (Новосибирск)
Статистика доступов: архив | текущая статистика
 

Документ изменен: Wed Feb 27 14:26:40 2019. Размер: 13,294 bytes.
Посещение N 1225 c 05.08.2014