Global Methods for Combinatorial Isoperimetric Problems
With a focus on global methods, this innovative text employs morphisms to transform new problems into more restricted and easily solvable settings while preserving essential structure.
TABLE OF CONTENTS Global Methods for Combinatorial Isoperimetric Problems
6.4: The Bezrukov Das Els sser Theorem
6.4 The Bezrukov Das Els sser Theorem
6.4.1 The Petersen graph and its products
Denote by P the Petersen graph (diagrammed in Fig. 6.1 ). The Petersen graph is a favorite with combinatorialists because of its unusual and extremal properties. It has the reputation of being a universal counterexample, the rock upon which many a pretty conjecture has foundered. It is the logo of the Journal of Graph Theory and there is even a book devoted to its lore [55].
Fig. 6.1: The Petersen graph.
Let P d = P P P, the d-fold product of Petersen graphs. Bezrukov, Els sser & Das [18], motivated by computer scientists interested in using P d as the connection graph for multiprocessing computers, solved the EIP for P d. Their solution and proof, which we now turn to, is a beautiful illustration of the power of compression and may well point the way for future developments.
6.4.2 The solution for d = 1
Lemma 6.5
The Petersen graph has nested solutions, maximizing E ( S) , the number of induced edges, over all S ? V with S = k. The initial segments of the numbering, 
1 , shown in Fig. 6.1 are such optimal sets.
Proof P has girth (the minimum length of a circuit) of 5. Thus for 0 ? k < 5 , solution sets induce trees, and for k =...
Copyright Cambridge University Press 2004 under license agreement with Books24x7
