10
$\begingroup$

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.

$\endgroup$

4 Answers 4

6
$\begingroup$

Here is a more general family of graphs:

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.

$\endgroup$
3
$\begingroup$

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 confusion 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. For example if $G$ is a minimally 2-connected graph, then subdividing any edge of $G$ (at least twice) yields a minimally 2-connected graph. Thanks to Jukka Suomela for pointing out an error in an earlier version of this answer (see the comment below).

$\endgroup$
1
  • 3
    $\begingroup$ 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). $\endgroup$ Aug 14, 2010 at 10:58
1
$\begingroup$

I conjecture that a a sufficient condition for a graph being minimally 2-vertex-connected is that

  • it is $2$-vertex-connected and if every vertex $u$ is adjacent to some vertex $v$ of degree $2$ and consequently,

  • if $u$ is of degree $2$ then there exists at least one edge $e_{uv}$ that is adjacent to $u$ and another vertex $v$ that is also of degree $2$

$\endgroup$
2
  • $\begingroup$ This is obviously a sufficient condition. Did you mean to conjecture that it is also necessary? $\endgroup$ Dec 9, 2023 at 12:38
  • $\begingroup$ @BrendanMcKay no, I know that there are other graphs that are minimally 2-vertex connected, that don't have any bivalent vertices $\endgroup$ Dec 9, 2023 at 20:13
0
$\begingroup$

$K_3$ is the only graph with a triangle that contains a bivalent vertex, and is a minimally vertex 2-connected graph (MV2CG).

According to the two ears theorem every triangulated polygon with at least four vertices contains at least two triangles with bivalent vertices and are thus not a MV2CG; that, can however easily be "healed" by splitting these bivalent vertices and connecting corresponding copies with an edge.
Further edges can be added to these kind of MV2CGs without losing the MV2CG property by augmenting pairs of triangles, that share an edge, with the edge that connects their yet unconnected pair of vertices as depicted below:

enter image description here

$\endgroup$

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.