On bounds for the \(k\)-partitioning of graphs (Q4938663)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1405682
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On bounds for the \(k\)-partitioning of graphs |
scientific article; zbMATH DE number 1405682 |
Statements
On Bounds for the k-Partitioning of Graphs (English)
0 references
On bounds for the \(k\)-partitioning of graphs (English)
0 references
29 November 2000
0 references
partitioning of graphs
0 references
isoperimetric problem
0 references
Hamming graphs
0 references
0.9629705
0 references
0.9612313
0 references
0.9605374
0 references
0.95048964
0 references
0 references
0 references
0.9375508
0 references
0.93672967
0 references
Let a graph on \(n\) vertices and a natural number \(k\) be given. What is the minimum size of an edge cut (the minimum number of edges that must be removed) such that the resulting graph splits into \(k\) connected components, each of cardinality \(\lfloor n/k\rfloor\) or \(\lceil n/k\rceil ?\) The authors establish a link to the edge-isoperimetric problem and use it to obtain bounds for Hamming graphs (also known as Hamming scheme) and related families of graphs. For the entire collection see [Zbl 0918.00033].
0 references
