On \(k\)-partitioning of Hamming graphs
type: Item
instance of: scholarly article
title: On \(k\)-partitioning of Hamming graphs
zbMATH Open document ID: 0934.05101
DOI: 10.1016/S0166-218X(99)00070-0
author: U.-P. Schroeder
author: Sergej L. Bezrukov
author: Robert Elsässer
published in: Discrete Applied Mathematics
publication date: 2000-04-09T00:00:00Z
review text: For a graph \(G=(V,E)\) a \(k\)-partition is a partition \(A=\{A_1, A_2, \dots, A_k \}\) of \(V\) such that \(||A_i|- |A_j||\leq 1\) for all \(i,j\in \{1,2,\dots, k\}\). A cut of partition \(A\) is a set of edges having ends in different sets of the partition. The authors investigate the problem of determining \(k\)-partitions with minimal cardinality cut. Several interesting bounds and asymptotic results for some specific values of \(k\) are presented for Hamming graphs (Cartesian products of complete graphs).
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1340631
zbMATH Keywords: graph partitioning
zbMATH Keywords: edge-isoperimetric problem
zbMATH Keywords: Hamming graphs
zbMATH Keywords: hypercubes
reviewed by: Fedor V. Fomin
MaRDI profile type: Publication
full work available at URL: s0166-218x(99)00070-0
OpenAlex ID: W2037594260
Wikidata QID: Q127646775
description: scientific article; zbMATH DE number 1340631