Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Given an unweighted graph $G = (V, E)$, let the cut function on this graph be defined to be: $C:2^V \rightarrow \mathbb{Z}$ such that: $$C_G(S) = |\{(u,v) \in E : u \in S \wedge v \not\in S\}|$$

For any two vertices $i,j \in V$, let the $(i,j)$ min-cut in a graph $G$ be: $$\alpha_{i,j}(G) = \min_{S \subset V : i \in S, j \not \in S}C_G(S)$$ Now, suppose we have two unweighted graphs on the same vertex set, $G = (V,E)$ and $H = (V,E')$ such that they are identical with respect to all $(i,j)$ min-cuts: $$\forall i,j \in V, \alpha_{i,j}(G) = \alpha_{i,j}(H)$$ How much can $H$ and $G$ differ with respect to their cuts? That is, how large can the following quantity be: $$\Delta(H,G) = \max_{S \subset V} |C_G(S) - C_H(S)|$$

Note that if the graphs are allowed to be weighted (or to be multigraphs), then for any $G$, there is a tree $T$ that agrees with $G$ on all min-cuts (A Gomory-Hu tree). But I am interested in the case of unweighted graphs...

share|improve this question
    
I love how it's "function of a graph" instead of "graph of a function" –  David Corwin Aug 24 '10 at 21:52

1 Answer 1

up vote 6 down vote accepted

If G and H are graphs with n vertices, Δ(G,H) can be Θ(n2).

Here is an example which shows this. Let n=4k+1 be a prime. Define two graphs G=(V,E) and H=(V,E′) by V={0,1,2,…,4k}, E = {{i,j} | 1 ≤ ((j−i) mod n) ≤ k}, E′ = {{i,j} | k+1 ≤ ((j−i) mod n) ≤ 2k}. Note that G and H are both unions of k edge-disjoint Hamiltonian circuits, which implies that αi,j(G)=αi,j(H)=2k for any distinct i and j. Let S={0,1,2,…,2k−1}. Then Δ(G,H) ≥ CH(S)−CG(S) = k(3k+1)−k(k+1) = 2k2 = Θ(n2).

There is no reason to believe that this is the maximum of Δ(G,H) for given n, but it is obviously optimal up to a constant factor.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.