Isoperimetric Tools

Solution of the EIP for the Cartesian product of two graphs

This tool is intended for solving the Edge-Isoperimetric Problem (EIP) on the cartesian product of two graphs. See here for the problem statement. The cartesian product G x H of graphs G and H is defined as follows. The vertex set of G x H is the cartesian product of the vertex sets of G and H, and the pairs (p₁, q₁) and (p₂, q₂) form an edge in G x H iff p₁ = p₂ and (q₁, q₂) is an edge of H, or q₁ = q₂ and (p₁, p₂) is an edge of G.

The default values in the input fields below correspond to the Petersen graph. Thus, this tool provides a numeric solution to the edge-isoperimetric problem on the Cartesian product of two Petersen graphs, which is mentioned in [2] without a proof.

Clicking on the button causes sending your data to the server for processing. The processing consists of generating all compressed sets in G x H, or, in other terms, all ideals in the |G| x |H| grid, and computing the goal function for each of them. The program is based on an algorithm from [1]. Since the number of ideals equals the order of the poset L(|G|, |H|), which is the binomial coefficient C(|G|+|H|, |G|), the computations might take some time. The current process status is indicated by the progress bar.

After computing the goal function for G x H, the program checks the existence of nested solutions (NSS). If nested solutions do exist, the system displays one of the total orders. Otherwise, one of the longest initial nested series will be shown.

References

[1] X. Berenguer, L.H. Harper: Estabilizacion y resolucion de algunos problemas combinatorios en grafos simetricos, Questio, vol. 3 (1979), No. 2, 105-117.

[2] S.L. Bezrukov, S. Das, R. Elsässer: An edge isoperimetric problem for powers of the Petersen graph, Annals of Combinatorics, vol. 4 (2000), 153-169.

[3] S.L. Bezrukov: On an equivalence in discrete extremal problems, Discr. Math., vol. 203, 1999, no. 1, 9-22.