Muutke küpsiste eelistusi

Circuit Double Cover of Graphs [Pehme köide]

4.00/5 (1 hinnangut Goodreads-ist)
(West Virginia University)
  • Formaat: Paperback / softback, 375 pages, kõrgus x laius x paksus: 226x152x20 mm, kaal: 560 g, Worked examples or Exercises; 120 Line drawings, unspecified
  • Sari: London Mathematical Society Lecture Note Series
  • Ilmumisaeg: 26-Apr-2012
  • Kirjastus: Cambridge University Press
  • ISBN-10: 0521282357
  • ISBN-13: 9780521282352
Teised raamatud teemal:
Circuit Double Cover of GraphsSuurem pilt
  • Formaat: Paperback / softback, 375 pages, kõrgus x laius x paksus: 226x152x20 mm, kaal: 560 g, Worked examples or Exercises; 120 Line drawings, unspecified
  • Sari: London Mathematical Society Lecture Note Series
  • Ilmumisaeg: 26-Apr-2012
  • Kirjastus: Cambridge University Press
  • ISBN-10: 0521282357
  • ISBN-13: 9780521282352
Teised raamatud teemal:
Püsilink: https://www.kriso.ee/db/9780521282352.html
Märksõnad:
The famous Circuit Double Cover conjecture (and its numerous variants) is considered one of the major open problems in graph theory owing to its close relationship with topological graph theory, integer flow theory, graph coloring and the structure of snarks. It is easy to state: every 2-connected graph has a family of circuits covering every edge precisely twice. C.-Q. Zhang provides an up-to-date overview of the subject containing all of the techniques, methods and results developed to help solve the conjecture since the first publication of the subject in the 1940s. It is a useful survey for researchers already working on the problem and a fitting introduction for those just entering the field. The end-of-chapter exercises have been designed to challenge readers at every level and hints are provided in an appendix.

Arvustused

"This book draws a comprehensive panoramic image of material from a large number of results spread through various papers.The most essential of these results are virtually rewritten, and the fabric of connections among them is revealed. The author establishes a uniform framework in which most of the work done so far, as well as potential directions for future work, is described and can be understood in a clear and systematic manner. The book is recommended to researchers and students interested in graph theory." Martin Kochol, Mathematical Reviews

Muu info

Contains all the techniques, methods and results developed so far in a bid to solve the famous CDC conjecture.
Foreword xiii
Brian Alspach
Foreword xv
Michael Tarsi
Preface xix
1 Circuit double cover 1(9)
1.1 Circuit double cover conjecture
2(1)
1.2 Minimal counterexamples
3(2)
1.3 3-edge-coloring and even subgraph cover
5(1)
1.4 Circuit double covers and graph embeddings
6(2)
1.5 Open problems
8(1)
1.6 Exercises
8(2)
2 Faithful circuit cover 10(11)
2.1 Faithful circuit cover
10(3)
2.2 3-edge-coloring and faithful cover
13(1)
2.3 Construction of contra pairs
14(4)
2.4 Open problems
18(1)
2.5 Exercises
19(2)
3 Circuit chain and Petersen minor 21(14)
3.1 Weight decomposition and removable circuit
21(1)
3.2 Cubic minimal contra pair
22(3)
3.3 Minimal contra pair
25(3)
3.4 Structure of circuit chain
28(3)
3.5 Open problems
31(1)
3.6 Exercises
31(4)
4 Small oddness 35(10)
4.1 k-even subgraph double covers
35(2)
4.2 Small oddness
37(6)
4.3 Open problems
43(1)
4.4 Exercises
44(1)
5 Spanning minor, Kotzig frames 45(21)
5.1 Spanning Kotzig subgraphs
45(6)
5.2 Kotzig frames
51(5)
5.3 Construction of Kotzig graphs
56(2)
5.4 Three-Hamilton circuit double covers
58(3)
5.5 Open problems
61(2)
5.6 Exercises
63(3)
6 Strong circuit double cover 66(17)
6.1 Circuit extension and strong CDC
66(1)
6.2 Thomason's lollipop method
67(3)
6.3 Stable circuits
70(1)
6.4 Extension-inheritable properties
71(3)
6.5 Extendable circuits
74(2)
6.6 Semi-extension of circuits
76(3)
6.7 Circumferences
79(1)
6.8 Open problems
80(1)
6.9 Exercises
81(2)
7 Spanning trees, supereulerian graphs 83(13)
7.1 Jaeger Theorem: 2-even subgraph covers
83(2)
7.2 Jaeger Theorem: 3-even subgraph covers
85(2)
7.3 Even subgraph 2k-covers
87(2)
7.4 Catlin's collapsible graphs
89(4)
7.5 Exercises
93(3)
8 Flows and circuit covers 96(16)
8.1 Jaeger Theorems: 4-flow and 8-flow
96(1)
8.2 4-flows
97(4)
8.3 Seymour Theorem: 6-flow
101(3)
8.4 Contractible configurations for 4-flow
104(1)
8.5 Bipartizing matching, flow covering
105(3)
8.6 Exercises
108(4)
9 Girth, embedding, small cover 112(5)
9.1 Girth
112(1)
9.2 Small genus embedding
112(3)
9.3 Small circuit double covers
115(1)
9.4 Exercises
116(1)
10 Compatible circuit decompositions 117(17)
10.1 Introduction
117(1)
10.2 Relation with faithful circuit cover
118(3)
10.3 Counterexample's and graph minor related results
121(1)
10.4 Planar graphs
122(3)
10.5 Dominating circuit mid Sabidussi Conjecture
125(1)
10.6 Construct km of contra pairs
126(4)
10.7 Open problems
130(1)
10.8 Exercises
131(3)
11 Other circuit decompositions 134(3)
11.1 Restricted circuit decompositions
134(2)
11.2 Open problems
136(1)
11.3 Exercises
136(1)
12 Reductions of weights, coverages 137(16)
12.1 Weight reduction for contra pairs
137(13)
12.2 Coverage reduction with fixed parity
150(1)
12.3 Exercises
151(2)
13 Orientable cover 153(10)
13.1 Orientable double cover
153(4)
13.2 Circular double covers and modulo orientations
157(4)
13.3 Open problems
161(1)
13.4 Exercises
162(1)
14 Shortest cycle covers 163(26)
14.1 Shortest cover and double cover
163(3)
14.2 Minimum eulerian weight
166(2)
14.3 3-even subgraph covers
168(18)
14.3.1 Basis of cycle space
168(1)
14.3.2 3-even subgraph covers
169(2)
14.3.3 (> or = to 4)-even subgraph covers
171(1)
14.3.4 Upper bounds of SCC3
171(1)
14.3.5 Relations with other major conjectures
172(2)
14.3.6 Fano plane and Fano flows
174(5)
14.3.7 Incomplete Fano flows, Fµ-flows
179(3)
14.3.8 Some proofs
182(4)
14.4 Open problems
186(1)
14.5 Exercises
187(2)
15 Beyond integer (1,2)-weight 189(10)
15.1 Rational weights
190(3)
15.2 Group weights
193(1)
15.3 Integer weights
194(3)
15.3.1 Non-negative weights and Petersen minor
194(1)
15.3.2 Integer semi-group weights
194(1)
15.3.3 Small range
195(2)
15.4 Open problems
197(1)
15.5 Exercises
197(2)
16 Petersen chain and Hamilton weights 199(44)
16.1 Local structures
200(2)
16.2 Hamilton weight
202(2)
16.3 (K4)-graphs
204(8)
16.4 P10-free Hamilton weighted graphs
212(4)
16.5 Circuit chain and Petersen chain
216(21)
16.6 Minimal contra pair
237(1)
16.7 Open problems
238(1)
16.8 Exercises
239(4)
Appendix A Preliminary 243(9)
A.1 Fundamental theorems
243(4)
A.2 Even subgraphs and parity subgraphs
247(3)
A.3 Exercises
250(2)
Appendix B Snarks, Petersen graph 252(21)
B.1 3-edge-coloring of cubic graphs, snarks
252(8)
B.1.1 Parity lemma
253(1)
B.1.2 Snarks
253(1)
B.1.3 Construction of snarks
254(2)
B.1.4 Girths and bonds of snarks
256(2)
B.1.5 Small snarks
258(2)
B.2 A mini encyclopedia of the Petersen graph
260(8)
B.3 Exercises
268(1)
B.4 Various drawings of the Petersen graph
269(4)
Appendix C Integer flow theory 273(12)
C.1 Tutte's integer flows
273(4)
C.2 Fundamental lemmas
277(2)
C.3 Exercises
279(6)
Appendix D Hints for exercises 285(37)
Glossary of terms and symbols 322(15)
References 337(14)
Author Index 351(3)
Subject Index 354
Cun-Quan Zhang is Eberly Distinguished Professor of Mathematics at West Virginia University.