Abstract:
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.
Fulltext:
PDF file (1228 kB)