Okamura H.'s 2-reducible cycles containing three consecutive edges in (2k PDF

By Okamura H.

Show description

Read or Download 2-reducible cycles containing three consecutive edges in (2k + 1)-edge-connected graphs PDF

Best graph theory books

Download e-book for kindle: Graph theory and combinatorial optimization by David Avis, Alain Hertz, Odile Marcotte

Graph conception is especially a lot tied to the geometric houses of optimization and combinatorial optimization. furthermore, graph theory's geometric homes are on the middle of many examine pursuits in operations study and utilized arithmetic. Its ideas were utilized in fixing many classical difficulties together with greatest stream difficulties, self sustaining set difficulties, and the touring salesman challenge.

Download e-book for iPad: An Algorithmic Theory of Numbers, Graphs and Convexity by Laszlo Lovasz

A examine of the way complexity questions in computing engage with classical arithmetic within the numerical research of concerns in set of rules layout. Algorithmic designers inquisitive about linear and nonlinear combinatorial optimization will locate this quantity specifically worthy. algorithms are studied intimately: the ellipsoid technique and the simultaneous diophantine approximation strategy.

Extra info for 2-reducible cycles containing three consecutive edges in (2k + 1)-edge-connected graphs

Example text

Discrete Math. 3, 145-164 (1978) 4. : Paths in graphs, reducing the edge-connectivity only by two. Graphs and Comb. I, 81-89 (1985) 5. : Paths and edge-connectivity in graphs. J. Comb. Theory Ser. B 37, 151172 (1984) 6. : Paths in k-edge-connected graphs. J. Comb. Theory Ser. B 45, 345-355 (1988) 7. : Cycles containing three consecutive edges in 2k-edge-connected graphs, Topics in Combinatorics and Graph Theory (eds. R. Bodendiek and R. Henn), PhysieaVerlag Heidelberg (1991), 549-553 8. : 2-reducible cycles containing two specified edges in (2k + 1)-edgeconnected graphs, Contemporary Math.

Bodendiek and R. Henn), PhysieaVerlag Heidelberg (1991), 549-553 8. : 2-reducible cycles containing two specified edges in (2k + 1)-edgeconnected graphs, Contemporary Math.

Then there are disjoint D~, D2 c_ V(G) - (X2 + vl) such that V(G) = Dx O D 2 (3 X 2 (J {01 }, e(D1, D2) --- 0, z 6 D1 and u 2 ~ D 2. 8). Thus Xx = DIUD2U{vl} = {vt,v2,z}. 6) e(z, X 2 ) < ~ and e(z, v l) < ~, a contradiction. 11), V(P*) = {u~, x, y, u2} for some x ~ X2 and y e X 1 . 23), there is (k + 3)-set Z with Z f ) ( T U {x,y})-(vl, u2, x}. e(X1 tq Z) >_ k + 4, and e(X1 tq Z) > k + 4 since X1 and X2 are minimal (k + 3)-sets, contrary to Lemma 2. 25), V(G) - T is an independent set. 22). 6).

Download PDF sample

2-reducible cycles containing three consecutive edges in (2k + 1)-edge-connected graphs by Okamura H.


by John
4.5

Rated 4.78 of 5 – based on 19 votes