1
$\begingroup$

Does there exists a connected graph G which is a subgraph of two graphs H and H' for which

  • G, H and H' have the same vertex set,
  • H is minimally 2-connected (i.e. deleting any edge from H makes is not 2-connected),
  • H' is 3-connected and
  • H is not a subgraph of H'?

I arrived at this question when thinking about how grant applications with "anti-terrorism" in the title seem to get much more funding than those without. I came out with this problem: A terrorist wants to disconnect G by deleting edges. To prepare for this attack, I want to add edges to G to make it 2-connected (i.e. H) at minimal cost, while at the same time preparing to make it 3-connected (i.e. H') at a later date. Does the choice of H matter?

$\endgroup$
1
  • 9
    $\begingroup$ Usually $k$-connected means "vertex $k$-connected" but if your hypothetical terrorists prefer cutting cables to blowing up relay stations, take a long path for $G$, make it into a single loop to get $H$ and add all edges except the edge that you used to get $H$ to get $H'$. Can I have my grant now? $\endgroup$
    – fedja
    May 16, 2010 at 0:02

1 Answer 1

4
$\begingroup$

Fedja's comment definitely earns the grant. A minimal example is to let G be a star with four leaves {1,2,3,4}, let H be the bowtie obtained from G be adding the edges 13 and 24, and let H' be the wheel obtained from G by adding the cycle 1234.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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