Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 659.05079
Autor: Erdös, Paul; Godsil, C.D.; Krantz, S.G.; Parsons, T.D.
Title: Intersection graphs for families of balls in Rn. (In English)
Source: Eur. J. Comb. 9, No.5, 501-506 (1988).
Review: Let B(x,r) denote a ball, (either open or closed) of radius r > 0 and center x, in the Euclidean space Rn. Let \mu[A] be the n-dimensional Lebesgue volume of the subset A of Rn and let \epsilon denote a real number in (0,1]. A pair of balls B, B' are said to be \epsilon-disjoint if \mu(B\cap B') \leq (1-\epsilon)max {\mu(B),\mu(B')}. A family F of balls is \epsilon-disjoint, if the balls are pairwise \epsilon-disjoint. Denote by \Gamman,\epsilon the set of all intersection graphs \Gamma(F) for \epsilon-disjoint families F of balls in Rn. The authors show that there exists a least integer d = d(n,\epsilon) such that every graph in \Gamman,\epsilon has a vertex of degree at most d and also show that there exists a least integer m = m(n) such that every intersection graph \Gamma(F), where F is a family of balls, has a vertex v such that the subgraph induced by the vertices adjacent to v contains no independent set of size greater than m.
Reviewer: R.C.Entringer
Classif.: * 05C99 Graph theory
Keywords: epsilon-disjoint; ball; Euclidean space; intersection graph
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag