Geodesic
Partitioning a $k$-connected graph
Diskretnaya Matematika, Tome 17 (2005) no. 3, pp. 112-122.

Voir la notice de l'article provenant de la source Math-Net.Ru

We study partitions of graphs by a system of disconnecting sets. We find a sharp upper bound for the number of resulting parts and analyse the case where the bound is attained. The result due to D. V. Karpov about the number of parts in a partition is proved under weaker constraints imposed on the graph. We also prove a theorem on bounding parts which yields an upper bound for the number of parts of the partition adjacent to a given vertex.This research was supported by the Program of Fundamental Research of Presidium of the Russian Academy of Sciences ‘Research in base fields of modern mathematics’ and by the Program of the President of the Russian Federation for supporting the leading scientific schools, grant 2203.2003.1. 
@article{DM_2005_17_3_a11,
     author = {Yu. M. Lifshits},
     title = {Partitioning a $k$-connected graph},
     journal = {Diskretnaya Matematika},
     pages = {112--122},
     publisher = {mathdoc},
     volume = {17},
     number = {3},
     year = {2005},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2005_17_3_a11/}
}
TY  - JOUR
AU  - Yu. M. Lifshits
TI  - Partitioning a $k$-connected graph
JO  - Diskretnaya Matematika
PY  - 2005
SP  - 112
EP  - 122
VL  - 17
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2005_17_3_a11/
LA  - ru
ID  - DM_2005_17_3_a11
ER  - 
%0 Journal Article
%A Yu. M. Lifshits
%T Partitioning a $k$-connected graph
%J Diskretnaya Matematika
%D 2005
%P 112-122
%V 17
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2005_17_3_a11/
%G ru
%F DM_2005_17_3_a11
Yu. M. Lifshits. Partitioning a $k$-connected graph. Diskretnaya Matematika, Tome 17 (2005) no. 3, pp. 112-122. http://geodesic.mathdoc.fr/item/DM_2005_17_3_a11/

[1] Kharari F., Teoriya grafov, Mir, Moskva, 1973 | MR

[2] Ore O., Teoriya grafov, Nauka, Moskva, 1968 | MR

[3] Matula D. W., “$k$-Blocks and ultrablocks in graphs”, J. Comb Theory, Ser. B, 24 (1978), 1–13 | DOI | MR | Zbl

[4] Harary F., Kodama Y., “On the genus of an $n$-connected graph”, Fund. Math., 54 (1964), 7–13 | MR | Zbl

[5] MacLane S., “A structural characterization of planar graph”, Duke Math. J., 3 (1937), 460–472 | DOI | MR | Zbl

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

[7] Hopcroft J. E., Tarjan R. E., “Dividing a graph into triconnected components”, SIAM J. Comput., 2 (1973), 135–158 | DOI | MR

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

[9] Karpov D. V., Pastor A. V., “O strukture $k$-svyaznogo grafa”, Zapiski nauchnykh seminarov POMI, 266 (2000), 76–106 | MR

[10] Karpov D. V., “Bloki v $k$-svyaznom grafe”, Zapiski nauchnykh seminarov POMI, 293 (2002), 59–93 | MR | Zbl

[11] Grekhem R., Knut D., Patashnik O., Konkretnaya matematika, Mir, Moskva, 1998

[12] Iverson K. E., A programming language, Wiley, New York, 1962 | MR | Zbl