Welcome to MathOverflow

Question

1

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?

flag	asked May 15 2010 at 23:47 Douglas S. Stones 2,956●1●12●31

8

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? – fedja May 16 2010 at 0:02

Thanks... that was actually pretty easy. (: – Douglas S. Stones May 16 2010 at 1:14

Tony Huynh · Accepted Answer · 2010-05-17 23:30:57Z UTC

4

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.

edited May 17 2010 at 23:30

answered May 16 2010 at 1:26

Tony Huynh
8,953●1●22●62

Thanks, I better accept an answer so this doesn't get listed as an open problem. – Douglas S. Stones May 21 2010 at 3:13

A minimally 2-connected graph H and a 3-connected graph H' both contain G, does H' contain H?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.