Press "Enter" to skip to content

2-reducible cycles containing three consecutive edges in (2k by Okamura H.

By Okamura H.

Show description

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

Best graph theory books

Graph Theory and combinatorics 1988, Proceedings of the Cambridge Combinatorial Conference in Honour of Paul Erdös

Combinatorics has no longer been a longtime department of arithmetic for extraordinarily lengthy: the final zone of a century has noticeable an explosive progress within the topic. This development has been principally as a result doyen of combinatorialists, Paul Erdos, whose penetrating perception and insatiable interest has supplied a massive stimulus for employees within the box.

Topological Crystallography: With a View Towards Discrete Geometric Analysis

Geometry in historic Greece is expounded to have originated within the interest of mathematicians in regards to the shapes of crystals, with that interest culminating within the class of normal convex polyhedra addressed within the ultimate quantity of Euclid’s components. considering the fact that then, geometry has taken its personal course and the learn of crystals has no longer been a imperative topic in arithmetic, except for Kepler’s paintings on snowflakes.

Imagery in Scientific Thought Creating 20th-Century Physics

One of many nice mysteries of the human brain is its energy to create new varieties of wisdom. Arthur I. Miller is a historian of technology whose strategy has been strongly inspired through present paintings in cognitive technological know-how, and during this e-book he indicates how the 2 fields will be fruitfully associated with yield new insights into the inventive approach.

Eigenspaces of graphs

Graph idea is a crucial department of up to date combinatorial arithmetic. through describing fresh leads to algebraic graph idea and demonstrating how linear algebra can be utilized to take on graph-theoretical difficulties, the authors supply new thoughts for experts in graph conception. The e-book explains how the spectral conception of finite graphs should be reinforced via exploiting homes of the eigenspaces of adjacency matrices linked to a graph.

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

Sample text

Y1 N ~) = k + 2 + e and X1 fq Y ~ X1, contrary to the minimality of X 1. Thus X1 - T and X2 - T are independent sets. In (A) and (B), if x e X1 vl, then e(x, X 2 ) > ~ + 1, and so IXxl = 2 since e(v~,X2)> 2, R 2 = (x) and e(v~) = k + 1, which contradicts e(v~)= k in (A). 11). In (T), we can choose P* such that IE(P*)N O(X1)I = 1. For otherwise, starting from Ux along P*, let z be the first vertex in X1, then X 2 ÷ v~ separates z from u2. 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.

Acknowledgment. The author would like to thank the referee for his helpful comments. References 1. : On a theorem of Mader. Discrete Mathematics 101, 49-57 (1992) 2. : Counterexamples to a conjecture of Mader about cycles through specified vertices in n-edge-connected graphs. Graphs and Comb. 8, 253-258 (1992) 3. : A reduction method for edge-connectivity in graphs. Ann. 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.

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

Rated 4.78 of 5 – based on 23 votes