×

zbMATH — the first resource for mathematics

Edge-isoperimetric problems for Cartesian powers of regular graphs. (English) Zbl 1070.68114
Summary: We consider an Edge-Isoperimetric Problem (EIP) on the Cartesian powers of graphs. One of our objectives is to extend the list of graphs for whose Cartesian powers the lexicographic order provides nested solutions for the EIP. We present several new classes of such graphs that include as special cases all presently known graphs with this property. Our new results are applied to derive best possible edge-isoperimetric inequalities for the Cartesian powers of arbitrary regular, resp. regular bipartite, graphs with a high density.

MSC:
68R10 Graph theory (including graph drawing) in computer science
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ahlswede, R.; Bezrukov, S.L., Edge isoperimetric theorems for integer point arrays, Appl. math. lett., 8, 75-80, (1995) · Zbl 0830.05040
[2] Ahlswede, R.; Cai, N., General edge-isoperimetric inequalities, part iia local-global principle for lexicographic solution, European J. combin., 18, 479-489, (1997) · Zbl 0878.05050
[3] S.L. Bezrukov, Encoding of analog signals for discrete binary channel, in: Proc. Int. Conf. on Algebraic and Combinatorial Coding Theory, Varna 1988, 12-16.
[4] S.L. Bezrukov, Edge isoperimetric problems on graphs, in: L. Lovász, A. Gyarfas, G.O.H. Katona, A. Recski, L. Szekely (Eds.), Graph Theory and Combinatorial Biology, Vol. 7, Bolyai Soc. Math. Stud., Budapest, 1999, pp. 157-197. · Zbl 0927.05080
[5] Bezrukov, S.L.; Das, S.; Elsässer, R., An edge-isoperimetric problem for powers of the Petersen graph, Ann. combin., 4, 153-169, (2000) · Zbl 0951.05053
[6] Bollobás, B.; Leader, I., Edge-isoperimetric inequalities in the grid, Combinatorica, 11, 299-314, (1991) · Zbl 0755.05045
[7] Carlson, T.A., The edge-isoperimetric problem for discrete tori, Discrete math., 254, 33-49, (2002) · Zbl 1004.05038
[8] Harper, L.H., Optimal assignment of numbers to vertices, J. sos. ind. appl. math., 12, 131-135, (1964) · Zbl 0222.94004
[9] Lindsey II, J.H., Assignment of numbers to vertices, Amer. math. monthly, 7, 508-516, (1964) · Zbl 0279.05019
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.