Back to Search Start Over

An isoperimetric lemma

Authors :
Arie Bialostocki
P. Dierker
Source :
Discrete Mathematics. 94:221-228
Publication Year :
1991
Publisher :
Elsevier BV, 1991.

Abstract

A continuous version of the following problem is solved: Let G be a multipartite graph with a given partition of its vertex set, A 1 ∪ A 2 ∪…∪ A N . Find the maximum possible number of edges in G such that G has no connected component with more than t vertices.

Subjects

Subjects :
Combinatorics
Connected component
Discrete mathematics
Vertex (graph theory)
Graph partition
Neighbourhood (graph theory)
Discrete Mathematics and Combinatorics
Mixed graph
Level structure
Multipartite graph
Bound graph
Theoretical Computer Science
Mathematics

Details

ISSN :
0012365X
Volume :
94
Database :
OpenAIRE
Journal :
Discrete Mathematics
Accession number :
edsair.doi.dedup.....070d61070b282b4950dcc3f38ec07afe
Full Text :
https://doi.org/10.1016/0012-365x(91)90027-y
Full Text Access
View/download PDF

Tools

Authors Abstract Subjects Details