Geodesic
Minimal biconnected graphs
Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part VI, Tome 417 (2013), pp. 106-127 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

A biconnected graph is called minimal, if it becomes not biconnected after deleting any edge. We consider minimal biconnected graphs that have minimal number of vertices of degree 2. Denote the set of all such graphs on $n$ vertices by $\mathcal GM(n)$. It is known that a graph from $\mathcal GM(n)$ contains exactly $\lceil\frac{n+4}3\rceil$ vertices of degree 2. We prove that for $k\ge1$ the set $\mathcal GM(3k+2)$ consists of all graphs of type $G_T$, where $T$ is a tree on $k$ vertices which vertex degrees do not exceed 3. The graph $G_T$ is constructed of two copies of the tree $T$: to each pair of correspondent vertices of these two copies that have degree $j$ in $T$ we add $3-j$ new vertices of degree 2 adjacent to this pair. Graphs of the sets $\mathcal GM(3k)$ and $\mathcal GM(3k+1)$ are described with the help of graphs $G_T$. 
@article{ZNSL_2013_417_a3,
     author = {D. V. Karpov},
     title = {Minimal biconnected graphs},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {106--127},
     year = {2013},
     volume = {417},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2013_417_a3/}
}
TY  - JOUR
AU  - D. V. Karpov
TI  - Minimal biconnected graphs
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2013
SP  - 106
EP  - 127
VL  - 417
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2013_417_a3/
LA  - ru
ID  - ZNSL_2013_417_a3
ER  - 
%0 Journal Article
%A D. V. Karpov
%T Minimal biconnected graphs
%J Zapiski Nauchnykh Seminarov POMI
%D 2013
%P 106-127
%V 417
%U http://geodesic.mathdoc.fr/item/ZNSL_2013_417_a3/
%G ru
%F ZNSL_2013_417_a3
D. V. Karpov. Minimal biconnected graphs. Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part VI, Tome 417 (2013), pp. 106-127. http://geodesic.mathdoc.fr/item/ZNSL_2013_417_a3/

[1] G. A. Dirac, “Minimally $2$-connected graphs”, J. reine and angew. Math., 268 (1967), 204–216 | MR

[2] M. D. Plummer, “On minimal blocks”, Trans. Amer. Math. Soc., 134 (1968), 85–94 | DOI | MR | Zbl

[3] W. T. Tutte, Connectivity in graphs, Univ. Toronto Press, Toronto, 1966 | MR | Zbl

[4] W. T. Tutte, “A theory of $3$-connected graphs”, Indag. Math., 23 (1961), 441–455 | MR

[5] W. Mader, “On vertices of degree $n$ in minimally $n$-connected graphs and digraphs”, Combinatorics, Paul Erdős is Eighty, v. 2, Budapest, 1996, 423–449 | MR | Zbl

[6] W. Mader, “Zur Struktur minimal $n$-fach zusammenhängender Graphen”, Abh. Math. Sem. Univ. Hamburg, 49 (1979), 49–69 | DOI | MR | Zbl

[7] J. G. Oxley, “On some extremal connectivity results for graphs and matroids”, Discrete Math., 41 (1982), 181–198 | DOI | MR | Zbl

[8] W. Hohberg, “The decomposition of graphs into $k$-connected components”, Discr. Math., 109 (1992), 133–145 | DOI | MR | Zbl

[9] D. V. Karpov, A. V. Pastor, “O strukture $k$-svyaznogo grafa”, Zap. nauchn. semin. POMI, 266, 2000, 76–106 | MR | Zbl

[10] D. V. Karpov, “Bloki v $k$-svyaznykh grafakh”, Zap. nauchn. semin. POMI, 293, 2002, 59–93 | MR | Zbl

[11] D. V. Karpov, “Razdelyayuschie mnozhestva v $k$-svyaznom grafe”, Zap. nauchn. semin. POMI, 340, 2006, 33–60 | MR | Zbl

[12] D. V. Karpov, “Derevo razbieniya dvusvyaznogo grafa”, Zap. nauchn. semin. POMI, 417, 2013, 87–105