Annals of Combinatorics 4 (2000) 153-169


An Edge-Isoperimetric Problem for Powers of the Petersen Graph

Sergei L. Bezrukov, Sajal K. Das, and Robert Elsässer

Department of Mathematics and Computer Science, University of Wisconsin-Superior, Superior WI 54880, USA
sb@math.uwsuper.edu

Department of Computer Science and Engineering, University of Texas at Arlington, Arlington, TX 76019-0015, USA
das@cse.uta.edu

Department of Mathematics and Computer Science, University of Paderborn, 33095 Paderborn, Germany
elsa@uni-paderborn.de

Received August 20, 1999

AMS Subject Classification: 05C35, 05D05

Abstract. In this paper we introduce a new order on the set of n-dimensional tuples and prove that this order preserves nestedness in the edge isoperimetric problem for the graph Pn, defined as the nth cartesian power of the well-known Petersen graph. The cutwidth and wirelength of Pn are also derived. These results are then generalized for the cartesian product of Pn and the m-dimensional binary hypercube.

Keywords: isoperimetric problem, Petersen graph, wirelength, cutwidth


References

1.  R. Ahlswede and S.L. Bezrukov, Edge isoperimetric theorems for integer point arrays, Appl. Math. Lett. 8 (1995) 75–80.

2.  R. Ahlswede and N. Cai, General edge-isoperimetric inequalities, Part II: A local-global principle for lexicographic solution, Europ. J. Combin. 18 (1997) 479–489.

3.  S.L. Bezrukov, On an equivalence in discrete extremal problems, Discrete Math. 203 (1999) 9–22.

4.  S.L. Bezrukov, Edge isoperimetric problems on graphs, In: Graph Theory and Combinatorial Biology, L. Lov´asz, A. Gyarfas, G.O.H. Katona, A. Recski, and L. Szekely, Eds., Bolyai Socisty of Mathematical Studies, Vol. 7, Budapest, 1999, pp. 157–197.

5.  S.L. Bezrukov and R. Elsässer, Edge-isoperimetric inequalities for products of regular graphs, preprint.

6.  B. Bollobás and I. Leader, An isoperimetric inequality on the discrete torus, SIAM J. Appl. Math. 3 (1990) 32–37.

7.  B. Bollobás and I. Leader, Edge-isoperimetric inequalities in the grid, Combinatorica 11 (1991) 299–314.

8.  J.D. Chavez and L.H. Harper, Discrete isoperimetric problems and pathmorphisms, preprint.

9.  S.K. Das, M. Ibel, D. Hohndel, and S. Öhring, Efficient communication in the folded Petersen networks, Int. J. Foundations of Computer Science 8 (1997) 163–185.

10.  L.H. Harper, A necessary condition on minimal cube numberings, J. Appl. Prob. 4 (1967) 397–401.

11.  L.H. Harper, Optimal assignment of numbers to vertices, J. Sos. Ind. Appl. Math. 12 (1964) 131–135.

12.  J.H. Lindsey II, Assignment of numbers to vertices, Amer. Math. Monthly 7 (1964) 508– 516.

13.  S. Öhring and S.K. Das, The folded Petersen network: A new communication-efficient multiprocessor topology, In: Proc. Int. Conf. on Parallel Process., Vol. 1, CRC Press, Boca Raton, Florida, 1993, pp. 311–314.

14.  S. Öhring and S.K. Das, The folded Petersen network: A new versatile multiprocessor interconnection topology, In: Proc. Int. Workshop on Graph-Theoretic Concepts in Computer Science (WG’93), Lecture Notes in Computer Science, Vol. 790, Springer-Verlag, 1993, pp. 301–314.

15.  S. Öhring and S.K. Das, Efficient communication in the folded Petersen interconnection networks, In: Proc. Conf. Parallel Architectures and Languages Europe, Lecture Notes in Computer Science, Vol. 817, Springer-Verlag, 1994, pp. 25–34.

16.  S. Öhring and S.K. Das, The folded Petersen cube networks: New competitors for the hypercube, In: Proc. 5th IEEE Symp. on Parallel and Distributed Processing, 1993, pp. 582–589.

17.  S. Öhring and S.K. Das, Folded Petersen cube networks: New competitors for the hypercube, IEEE Transactions on Parallel and Distributed Systems 7 (1996) 151–168.


Get the DVI | PS | PDF file of this abstract.