On the sphericity for the join of many graphs

✍ Scribed by Hiroshi Maehara

• Publisher: Elsevier Science
• Year: 1984
• Tongue: English
• Weight: 110 KB
• Volume: 49
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(84)90169-9

✦ Synopsis

It is proved that given any number of graphs of order at most n, the sphericity of their join does not exceed 2(n-1).

We introduce an adjacency relation into Euclidean n-space E" so that it may be regarded as an infinite graph: Two points x and y of E" are defined to be adjacent if and only if 0<[x-y[< 1, where [ I denotes the Euclidean norm. Then any nonempty subset X of E" induces a subgraph (X). An abstract graph G is said to be embeddable in Xc E n, denoted G e X, if G is isomorphic to (Y) for some yc X. The (unit) sphericity of (3, sph(G), is the smallest integer n such that GEE".

Sphericity can be viewed as a measure of graph dimension. This concept first appeared in Guttman [1], and is proposed again by Havel [2] and Maehara . (The term sphericity is due to Havel.) In [3], certain bounds on the sphericity for split graphs, trees, and complete bipartite graphs, are derived.

This note provides an upper bound on the sphericity for the join of many graphs. Given graphs G1, G2,..., Gin, the join GI+ G2+"" "+ Gra is the graph obtained from the disjoint union of G1, G2 ..... G,, by adding those edges which connect pairs of vertices from distinct graphs. The complete m-partite graph K(nl, n2 ..... nm) is the join of m edgeless graphs of order nl, n2,... , nm.

Theorem. sph(G1 + G2 +'" • + Gin) ~< 2(n -1), n = maxl (the order of Gi).

Corollary 1. sph(K(n, n ..... n)) <~ 2(n -1).

The element observation sph(K(2, 2)) = 2 and sph(K(3, 3)) = 4 (see Table 1]) can be extended to arbitrarily many parts by applying our theorem. Corollary 2. sph(K(2, 2 ..... 2)) = 2, sph(K(3, 3 ..... 3)) = 4.