文档介绍：Discrete Applied Mathematics 154 (2006) 1309–1313
= 2 for n4. Graphs with sphericity 1 (unit interval graphs) possess a forbidden
subgraph characterization [18]. However, the recognition problem for graphs with sphericity 2 (unit disk graphs [3,8])
is NP-hard [2]. Researchers have focused on computing the sphericity for special classes of graphs [5,6,10–12,14]
and on discovering general bounds for the sphericity in terms of various graph parameters [7,13,16,17]. Maehara [9]
obtained the following upper bound for the sphericity of a graph G in terms of the clique number (G), ., the largest
number of vertices in a clique (complete subgraph) of G.
Maehara’s inequality. If G is a non-complete graph with n vertices and clique number (G), then the sphericity of
G satisfies
sph(G)n − (G).
E-mail address: ******@ (. Michael).
0166-218X/$ - see front matter © 2006 Elsevier . All rights reserved.
doi:. . Michael, T. Quint / Discrete Applied Mathematics 154 (2006) 1309–1313
The inequality cannot be substantially improved; for each m = 1, 2,...Maehara exhibited a graph Gm satisfying
m = sph(Gm) =|V(Gm)|−(Gm) − 1.
Our main theorem gives a new inequality that relates the sphericity to the cliques of a graph G. Br