|
|
 |
| Àâòîðèçàöèÿ |
|
|
|
| Ïîèñê ïî óêàçàòåëÿì |
|
|
|
|
|
|
|
 |
|
|
|
| Diestel R. — Graph Theory |
|
|
|
| Ïðåäìåòíûé óêàçàòåëü |
Cut, minimal 22 88
Cut-cycle duality 136—138
Cut-edge see “Bridge”
Cutvertex 10 43—44
CYCLE 7—9
Cycle in multigraphs 25
Cycle with orientation 136—138
Cycle, directed 119
Cycle, double cover conjecture 141 144
Cycle, expected number 234
Cycle, Hamilton 144 213—228
Cycle, induced 7—8 21 47 86 111 117 290
Cycle, length 7
Cycle, long 8 26 64 118
Cycle, non-separating 47 86
Cycle, odd 15 99 117 290
Cycle, short 101 179—180 235 237
Cycle, space 21 23—24 27—28 47—49 85—86 89 92—93
Cycle, threshold function 247
Cycle-cut duality 136—138
Cyclomatic number 21
d(G) 5
D(V) 5
d(x,y) 8
Degeneracy see “Colouring number”
Degree 5
Degree, sequence 216
Deletion 4
Dense graphs 148 150
Density of pair of vertex sets 153
Density, edge density 148
Density, upper density 166
Depth-first search tree 13 27
Deuber, W. 197
diam(G) 8
Diameter 5—9 248
Diameter and girth 8
Diameter and radius 9
Diestel, R. 186 281
Difference of graphs 4
Digon see “Double edge”
Digraph see “Directed graph”
Dilworth, R.P. 40 285 294
Dirac, G.A. 111 186 187 214 226
Directed cycle 119
Directed edge 25
Directed graph 25 108 119
Directed path 39
Direction 124
Disjoint graphs 3
Distance 8
Double counting 75 92 114—115 234 244
Double edge 25
Double wheel 208
Drawing 67 76—80
Drawing convex 92
Drawing straight-line 90
Dual and connectivity 91
Dual, abstract 55—89 91
Dual, plane 81 91
Duality of plane multigraphs 87—89
Duality, cycles and cuts 23—24 88—89 136
Duality, flows and colourings 136—139 291
E(G) 2
E(v), E'(w), ... 2
E(X) 231
E(X,Y), E'(U,W), ... 2
EDGE 2
Edge colouring 96 103—105 191
Edge colouring and flow number 135
Edge colouring and matchings 119
Edge contraction 16
Edge contraction and 3-connectedness 45
Edge contraction in multigraph 25
Edge contraction vs. minors 17
Edge cover 119
Edge density 5 148
Edge density and average degree 5
Edge density and regularity lemma 154 166
Edge density, forcing minors/topological minors 169—180
Edge density, forcing subgraphs 147—167
Edge of a multigraph 25
Edge space 20 85
Edge, crossing a partition 21
Edge, directed 25
Edge, double 25
Edge, plane 10
Edge, X-Y edge 2
Edge-chromatic number see “Chromatic index”
Edge-connectivity 11 55 58
Edge-disjoint spanning trees 58—61
Edge-maximal 4
Edge-maximal vs. extremal 149 182
Edge-maximal without  183
Edge-maximal without  182
Edge-maximal without  ,  84
Edge-maximal without 185
Edmonds, J. 42 282
Embedding in  69—70 77
Embedding in surface 74 92 274—276 280 281—282
Embedding in the plane 16 80—93
Embedding of bipartite graphs 202—204
Empty graph 2
End of edge 2 25
End of path 6
Endpoints of arc 68
Endvertex 2 25
Endvertex, terminal vertex 25
Equivalence in quasi-order 211
Equivalence of planar embeddings 76—80 19 90
Equivalence of points in  68
Erdos — Sos conjecture 152 166 167
Erdos, P. 101 121 151 152 163 166 167 187 191 208 209 210 215 228 232 235—231 243 249 295
Euler, characteristic 276
Euler, formula 74—75 89 90 289
Euler, L. 18—19 14
Euler, tour 19—20 291
Eulerian graph 19
Even, degree 19 33
Even, graph 133 135 145
Event 231
Evolution of random graphs 241 249
ex(n,H) 149
Exceptional set 153
Excluded minors see “Forbidden minors”
Existence proof, probabilistic 121 229 233 235—237
Expanding a vertex 113
Expectation 233—234 242
Exterior face see “Outer face”
Externally k-connected 264 280
Extremal vs. edge-maximal 149 182
Extremal without 183
Extremal without 182
Extremal without 184
Extremal without 185
Extremal, bipartite graph 165
Extremal, graph 149—150
Extremal, graph theory 147 151 160 166
F(G) 70
f(X,Y), g(U,W), ... 124
Face 70
Factor 29
Factor, 1-factor 29—38
Factor, 1-factor theorem 35 42 66
Factor, 2-factor 33
Factor, k-factor 29
Factor-critical 36 285
Fajtlowicz, S. 187
Fan 55
Fan-version of Menger’s theorem 55
| Finite graph 2
First order sentence 239
First point on frontier 68
Five colour theorem 96 121 141
Five colour theorem, list version 106 121
Five-flow conjecture 140 141
Fleischner, H. 218 295
Flow 123—146 125—126
Flow in plane graphs 136—139
Flow number 131—134 140 144
Flow, 2-flow 133
Flow, 3-flow 133—134 141
Flow, 4-flow 134—135 140—141
Flow, 6-flow theorem 141—143
Flow, conjectures 140—141
Flow, group-valued 128—133 144
Flow, H-flow 128—133
Flow, integral 126 128
Flow, k-flow 131—134 140—143 145
Flow, network flow 125—128 291
Flow, polynomial 130 146
Flow, total value of 126
Flow-colouring duality 136—139 291
Forbidden minors and chromatic number 181—185
Forbidden minors and tree-width 263—274
Forbidden minors, expressed by 263 274—277
Forbidden minors, minimal set of 274 280 281
Forbidden minors, planar 264
Forcibly hamiltonian see “Hamiltonian sequence”
Forcing  179—184 186
Forcing 184 187
Forcing  61 170—178 186
Forcing, high connectivity 11
Forcing, induced trees 178
Forcing, large chromatic number 101—103
Forcing, linkability 62—63 66 171—174
Forcing, long cycles 8 26 118 213—228
Forcing, long paths 8 166
Forcing, minor with large minimum degree 174 179
Forcing, short cycles 179—180 237
Forcing, subgraph 13 147—167
Forcing, tree 13 178
Forcing, triangle 119 209
Ford, L.R. Jr. 127 145
Forest 12
Forest, minor 281
Forest, partitions 60—61
Four colour problem 120 186
Four colour theorem 96 141 145 181 183 185 215 227
Four colour theorem, history 120—121
Four-flow conjecture 140—141
Frank, A. 65 145
Frobenius, F.G 42
From ... to 6
Frontier 68
Fulkerson, D.R. 122 127 145
g(G) 7
Gallai — Edmonds matching theorem 36—38 42
Gallai, T. 39 42 66 167
Galvin, F. 109
Gasparian, G.S. 122
Genus and colouring 121
Genus of a graph 90 280
Genus of a surface 276
Geometric dual see “Plane dual”
Gibbons, A. 145
Gilmore, P.C. 120
girth 7
Girth and average degree 237
Girth and chromatic number 101 121 235—237
Girth and connectivity 237
Girth and diameter 8
Girth and minimum degree 8 179—180 237
Girth and minors 179—180
Girth and planarity 89
Girth and topological minors 178
Godsil, C. 28
Golumbic, M.C. 122
Good characterization 274 282
Good pair 252
Good sequence 252
Gorbunov, K.Yu. 281
Goring, F. 66
Graham, R.L. 210
Graph 2—4 25 26
Graph, invariant 3
Graph, minor theorem 251 274—277 275
Graph, partition 60
Graph, plane 70—76 87—89 96—97 106—108 136—139
Graph, process 250
Graph, property 238
Graph, simple 26
Graph-theoretical isomorphism 77—78
Graphic sequence see “Degree sequence”
Greedy algorithm 98 108 117
grid 90 184 258
Grid, minor 260 264—274
Grid, theorem 264
Grid, tree-width of 260 278 281
Griinwald, T. 66
Grotzsch, H. 97 141 145
Group-valued flow 128—133
Guthrie, F. 120
Gyarfas, A. 178 185
Hadwiger, conjecture 169—170 181—183 185 186—187
Hadwiger, H. 181 186 187
Hajnal, A. 197 210
Hajos, construction 101—102
Hajos, G. 102 187
Haken, W. 121
Halin, R. 65—66 227 280—281
Hall, P. 31 42
Hamilton closure 226
Hamilton cycle 213—228
Hamilton cycle and 4-flows 144 215
Hamilton cycle and degree sequence 216—218 226
Hamilton cycle and minimum degree 214
Hamilton cycle and the four colour theorem 215
Hamilton cycle in  218—226
Hamilton cycle in  227
Hamilton cycle in almost all graphs 241
Hamilton cycle in planar graphs 215
Hamilton cycle, power of 226
Hamilton cycle, sufficient conditions 213—218
Hamilton path 213 218
Hamilton, W.R. 227
Hamiltonian sequence 216
Hamiltonian, graph 213
Harant, J. 66
head see “Terminal vertex”
Heawood, P.J. 121 145
Heesch, H. 121
Hereditary graph property 263 274—277
Hereditary graph property, algorithmic decidability 276—277
Higman, D.G. 252 280
Hoffman, A.J. 120
Hypergraph 25
In (a graph) 7
incidence 2
Incidence, encoding of planar embedding see “Combinatorial isomorphism”
Incidence, map 25—26
Incidence, matrix 24
incident 2 72
Increasing property 241 248
Independence number 110—117
Independence number and connectivity 214—215
Independence number and Hamilton cycles 215
Independence number and long cycles 118
Independence number and path cover 39
Independence number of random graph 232 248
|
|
|
| Ðåêëàìà |
|
|
|
|
|
Î ïðîåêòå