Sphericity, cubicity, and edge clique covers of graphs |
| |
| Authors: | TS Michael |
| |
| Institution: | a Mathematics Department, United States Naval Academy, Annapolis, MD 21402, USA
b Department of Mathematics and Statistics, University of Nevada, Reno, NV 89557, USA |
| |
| Abstract: | The sphericity 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 Rd. The edge clique cover number θ(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). Our upper bound remains valid for intersection graphs defined by balls in the Lp-norm for 1?p?∞. |
| |
| Keywords: | Intersection graph Sphericity Edge clique cover Cubicity |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
