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

A class of "minimally 2-vertex-connected graphs" - that is, 2-vertex-connected graphs which have the property that removing any one vertex (and all incident edges) renders the graph no longer 2-connected - have come up in my research.

Dirac wrote a paper on "minimally 2-connected graphs" (G. A. Dirac, Minimally 2-connected graphs, J. Reine Angew. Math. 228 (1967),. 204-216), which gives quite a detailed description of the structure of such graphs. However, in his sense, minimal 2-connectivity means that deleting any EDGE leaves a graph which is not 2-connected, which is not an equivalent property to the vertex-deletion one. Does anyone know anything about graphs with the latter property?

In the hope of stimulating some discussion, here is a wildly speculative and vague conjecture: The only graphs satisfying this property are simple cycles, and certain cycles with chords.

share|improve this question
add comment

2 Answers 2

up vote 2 down vote accepted

Here is a more general family:

Draw your favorite tree in the plane, with circles for the nodes and "thick" lines for the edges. Now turn every circle into a cycle, and every thick line into a pair of parallel paths $p_1, \ldots, p_m$ and $q_1, \ldots, q_n$ with various crossbraces. The crossbraces just have to follow the rule that if $p_i$ is connected to $q_\ell$ and $p_j$ is connected to $q_k$, for $i<j$ and $k<\ell$, then $j =i+1$ or $\ell=k+1$.

This is probably still not close to a complete characterization, but at least shows that the class is a lot broader than the small class you posited to promote discussion.

share|improve this answer
add comment

As the edited question mentions, Dirac did something similar, although minimality is with respect to edge deletion while connectivity is with respect to vertices (hence some confustion arose) The link is here.

I will mention that Chaty and Chein (1979) solved the problem where minimality is with respect to edge deletion, and connectivity is with respect to edges.

Also, I don't think that all such graphs are cycles with some chords, since subdividing any edge of a minimally 2-connected graph preserves minimal 2-connectivity. So, I can certainly destroy a chord by subdividing it.

share|improve this answer
2  
Regarding "subdividing any edge of a minimally 2-connected graph preserves minimal 2-connectivity": Consider a cycle with one chord $(u,v)$. Then subdivide the chord: add a new node $t$ and replace $(u,v)$ with the path $(u,t,v)$. The resulting graph is no longer minimally 2-connected: you can remove the node $t$ and you are left with a cycle which is 2-connected. However, if you add two nodes $s$ and $t$ and replace $(u,v)$ with the path $(u,s,t,v)$, then I think the new graph is minimally 2-connected (provided that in the cycle the distance between $u$ and $v$ is at least 3). –  Jukka Suomela Aug 14 '10 at 10:58
add comment

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.