Minimal Biconnected Graphs
| LEADER | caa a22 4500 | ||
|---|---|---|---|
| 001 | 605524971 | ||
| 003 | CHVBK | ||
| 005 | 20210128100756.0 | ||
| 007 | cr unu---uuuuu | ||
| 008 | 210128e20150101xx s 000 0 eng | ||
| 024 | 7 | 0 | |a 10.1007/s10958-014-2199-y |2 doi |
| 035 | |a (NATIONALLICENCE)springer-10.1007/s10958-014-2199-y | ||
| 100 | 1 | |a Karpov |D D. |u St.Petersburg Department of the Steklov Mathematical Institute, St. Petersburg State University, St. Petersburg, Russia |4 aut | |
| 245 | 1 | 0 | |a Minimal Biconnected Graphs |h [Elektronische Daten] |c [D. Karpov] |
| 520 | 3 | |a 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 GM(n). It is known that a graph from GM(n) contains exactly n + 4 3 $$ \left[\frac{n+4}{3}\right] $$ vertices of degree 2. We prove that for k ≥ 1, the set GM(3k + 2) consists of all graphs of the type G T , where T is a tree on k vertices the vertex degrees of which do not exceed 3. The graph G T is constructed from two copies of the tree T : to each pair of the corresponding 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 GM(3k) and GM(3k+1) are described with the help of graphs G T . Bibliography: 12 titles. | |
| 540 | |a Springer Science+Business Media New York, 2014 | ||
| 773 | 0 | |t Journal of Mathematical Sciences |d Springer US; http://www.springer-ny.com |g 204/2(2015-01-01), 244-257 |x 1072-3374 |q 204:2<244 |1 2015 |2 204 |o 10958 | |
| 856 | 4 | 0 | |u https://doi.org/10.1007/s10958-014-2199-y |q text/html |z Onlinezugriff via DOI |
| 898 | |a BK010053 |b XK010053 |c XK010000 | ||
| 900 | 7 | |a Metadata rights reserved |b Springer special CC-BY-NC licence |2 nationallicence | |
| 908 | |D 1 |a research-article |2 jats | ||
| 949 | |B NATIONALLICENCE |F NATIONALLICENCE |b NL-springer | ||
| 950 | |B NATIONALLICENCE |P 856 |E 40 |u https://doi.org/10.1007/s10958-014-2199-y |q text/html |z Onlinezugriff via DOI | ||
| 950 | |B NATIONALLICENCE |P 100 |E 1- |a Karpov |D D. |u St.Petersburg Department of the Steklov Mathematical Institute, St. Petersburg State University, St. Petersburg, Russia |4 aut | ||
| 950 | |B NATIONALLICENCE |P 773 |E 0- |t Journal of Mathematical Sciences |d Springer US; http://www.springer-ny.com |g 204/2(2015-01-01), 244-257 |x 1072-3374 |q 204:2<244 |1 2015 |2 204 |o 10958 | ||