×

Intersection graphs for families of balls in \(\mathbb{R}^n\). (English) Zbl 0659.05079

Let \(B(x,r)\) denote a ball, (either open or closed) of radius \(r>0\) and center x, in the Euclidean space \({\mathbb{R}}^n\). Let \(\mu[A]\) be the \(n\)-dimensional Lebesgue volume of the subset \(A\) of \({\mathbb{R}}^n\) 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)\min \{\mu(B),\mu(B')\}\). A family \(F\) of balls is \(\epsilon\)-disjoint, if the balls are pairwise \(\epsilon\)-disjoint. Denote by \(\Gamma_{n,\epsilon}\) the set of all intersection graphs \(\Gamma(F)\) for \(\epsilon\)-disjoint families \(F\) of balls in \({\mathbb{R}}^n\). The authors show that there exists a least integer \(d=d(n,\epsilon)\) such that every graph in \(\Gamma_{n,\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

MSC:

05C99 Graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Dirac, G. A., A property of 4-chromatic graphs and some remarks on critical graphs, J. London Math. Soc., 27, 85-92 (1952) · Zbl 0046.41001
[2] Federer, H., Geometric Measure Theory (1970), Springer-Verlag: Springer-Verlag Berlin · Zbl 0176.00801
[3] Fishburn, P. C., On the sphericity and cubicity of graphs, J. Comb. Theory, Ser. B, 35, 309-318 (1983) · Zbl 0533.05055
[4] Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York · Zbl 0541.05054
[5] Guttman, L., A definition of dimensionality and distance for graphs, (Lingoes, J. C., Geometric Representation of Relational Data (1977), Mathesis Press: Mathesis Press Michigan), 713-723
[6] Harary, F., Graph Theory (1969), Addison-Wesley: Addison-Wesley Reading, Mass. · Zbl 0797.05064
[7] Havel, T. F., The combinatorial distance geometry approach to the calculation of molecular conformation (1982), University of California: University of California Berkeley, Ph.D. Thesis, Group in Biophysics · Zbl 0516.05060
[8] Krantz, S. G.; Parsons, T. D., Antisocial subcovers of self-centered coverings, Amer. Math. Monthly, 93, 45-48 (1986) · Zbl 0631.52013
[9] Maehara, H., Space graphs and sphericity, Discr. Appl. Math., 7, 55-64 (1984) · Zbl 0527.05028
[10] Maehara, H., On the sphericity for the join of many graphs, Discr. Math., 49, 311-313 (1984) · Zbl 0544.05022
[11] Maehara, H., Contact patterns of equal nonoverlapping spheres, Graphs and Combinatorics, 1, 271-282 (1985) · Zbl 0581.05022
[12] Roberts, F. S., On the boxicity and cubicity of a graph, (Tutte, W. T., Recent Progress in Combinatorics (1969), Academic Press: Academic Press New York), 301-310 · Zbl 0193.24301
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.