| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 421038 | Discrete Applied Mathematics | 2006 | 5 Pages |
Abstract
The sphericity sph(G)sph(G) of a graph G is the minimum dimension d for which G is the intersection graph of a family of congruent spheres in RdRd. The edge clique cover number θ(G)θ(G) is the minimum cardinality of a set of cliques (complete subgraphs) that covers all edges of G. We prove that if G has at least one edge, then sph(G)⩽θ(G)sph(G)⩽θ(G). Our upper bound remains valid for intersection graphs defined by balls in the LpLp-norm for 1⩽p⩽∞1⩽p⩽∞.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
T.S. Michael, Thomas Quint,