×
Bezrukov, Sergei L.; Kuzmanovski, Nikola; Lim, Jounglag

Pull-push method: a new approach to edge-isoperimetric problems. (English) Zbl 1522.05078

Discrete Math. 346, No. 12, Article ID 113632, 21 p. (2023).
Summary: We prove a generalization of the Ahlswede-Cai local-global principle for the edge-isoperimetric problems. A new technique to handle edge-isoperimetric problems is introduced which we call the pull-push method. Our main result includes all previously published results in this area as special cases with the only exception of the edge-isoperimetric problem for grids. With this we partially answer a question of L. H. Harper [Global methods for combinatorial isoperimetric problems. Cambridge: Cambridge University Press (2004; Zbl 1043.05002)] on local-global principles. We also describe a strategy for further generalization of our results so that the case of grids would be covered, which would completely settle Harper’s question.

MSC:

05C12 Distance in graphs

Keywords:

Cartesian power; isoperimetric; edge-isoperimetric; local-global principle; inequality; pull-push method

Citations:

Zbl 1043.05002
Cite Review PDF
Full Text: DOI arXiv

References:

[1] Ahlswede, R.; Bezrukov, S. L., Edge isoperimetric theorems for integer point arrays, Appl. Math. Lett., 8, 2, 75-80 (1995) · Zbl 0830.05040
[2] Ahlswede, R.; Cai, N., General edge-isoperimetric inequalities. II. A local-global principle for lexicographical solutions, Eur. J. Comb., 18, 5, 479-489 (1997) · Zbl 0878.05050
[3] Ahlswede, R.; Cai, N., General edge-isoperimetric inequalities. I. Information-theoretical methods, Eur. J. Comb., 18, 4, 355-372 (1997) · Zbl 0940.05067
[4] Bernstein, A. J., Maximally connected arrays on the n-cube, SIAM J. Appl. Math., 15, 1485-1489 (1967) · Zbl 0157.26004
[5] Bezrukov, S.; Bulatovic, P.; Kuzmanovski, N., New infinite family of regular edge-isoperimetric graphs, Theor. Comput. Sci., 721, 42-53 (2018) · Zbl 1390.05197
[6] Bezrukov, S. L., Edge isoperimetric problems on graphs, (Graph Theory and Combinatorial Biology. Graph Theory and Combinatorial Biology, Balatonlelle, 1996. Graph Theory and Combinatorial Biology. Graph Theory and Combinatorial Biology, Balatonlelle, 1996, Bolyai Soc. Math. Stud., vol. 7 (1999), János Bolyai Math. Soc.: János Bolyai Math. Soc. Budapest), 157-197 · Zbl 0927.05080
[7] Bezrukov, S. L., On an equivalence in discrete extremal problems, Discrete Math., 203, 1-3, 9-22 (1999) · Zbl 0932.05044
[8] Bezrukov, S. L.; Elsässer, R., Edge-isoperimetric problems for Cartesian powers of regular graphs, Theor. Comput. Sci., 307, 3, 473-492 (2003) · Zbl 1070.68114
[9] Bezrukov, S. L.; Das, S. K.; Elsässer, R., An edge-isoperimetric problem for powers of the Petersen graph, Ann. Comb., 4, 2, 153-169 (2000) · Zbl 0951.05053
[10] Bollobás, B.; Leader, I., Edge-isoperimetric inequalities in the grid, Combinatorica, 11, 4, 299-314 (1991) · Zbl 0755.05045
[11] Bonnet, E.; Sikora, F., A note on edge isoperimetric numbers and regular graphs, Int. J. Found. Comput. Sci., 27, 6, 771-774 (2016) · Zbl 1352.05102
[12] Carlson, T. A., The edge-isoperimetric problem for discrete tori, Discrete Math., 254, 1-3, 33-49 (2002) · Zbl 1004.05038
[13] Das, S. K.; Hohndel, D. H.; Ibel, M.; Öhring, S. R., Efficient communication in folded petersen networks, Int. J. Found. Comput. Sci., 08, 02, 163-185 (1997)
[14] Harper, L. H., Optimal assignments of numbers to vertices, J. Soc. Ind. Appl. Math., 12, 131-135 (1964) · Zbl 0222.94004
[15] Harper, L. H., Global Methods for Combinatorial Isoperimetric Problems, Cambridge Studies in Advanced Mathematics, vol. 90 (2004), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1043.05002
[16] Hart, S., A note on the edges of the n-cube, Discrete Math., 14, 2, 157-163 (1976) · Zbl 0363.05058
[17] Lindsey, J. H., Assignment of numbers to vertices, Am. Math. Mon., 71, 508-516 (1964) · Zbl 0279.05019
[18] Ohring, S.; Das, S., Folded petersen cube networks: new competitors for the hypercubes, (Proceedings of 1993 5th IEEE Symposium on Parallel and Distributed Processing (1993)), 582-589
[19] Ohring, S.; Das, S., Folded petersen cube networks: new competitors for the hypercubes, IEEE Trans. Parallel Distrib. Syst., 7, 2, 151-168 (1996)
[20] Ohring, S.; Das, S. K., The folded petersen network: a new communication-efficient multiprocessor topology, (1993 International Conference on Parallel Processing - ICPP’93, vol. 1 (1993)), 311-314
[21] Öhring, S. R.; Das, S. K., The folded Petersen network: a new versatile multiprocessor interconnection topology, (Graph-Theoretic Concepts in Computer Science. Graph-Theoretic Concepts in Computer Science, Utrecht, 1993. Graph-Theoretic Concepts in Computer Science. Graph-Theoretic Concepts in Computer Science, Utrecht, 1993, Lecture Notes in Comput. Sci., vol. 790 (1994), Springer: Springer Berlin), 301-314 · Zbl 1528.68040
[22] Öhring, S. R.; Das, S. K., Efficient communication in the folded petersen interconnection network, (Proceedings of the 6th International PARLE Conference on Parallel Architectures and Languages Europe. Proceedings of the 6th International PARLE Conference on Parallel Architectures and Languages Europe, PARLE ’94 (1994), Springer-Verlag: Springer-Verlag Berlin, Heidelberg), 25-36
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.