Quadrilateral Embeddings of Composition Graphs 

The composition G[H] is formed by replacing each vertex of G with a copy of H and each edge of G with a regular complete bipartite graph connecting the corresponding new vertices. Let O(n) denote the graph on n vertices with no edges.

Problem: Characterize those graphs G for which the composition G[O(n)] ({n >= 3 odd) has a quadrilateral imbedding in an orientable surface.

Note that if G is triangle free, then the above embedding would be minimal. We specify that n is odd because the problem is completely solved for n even: any connected nontrivial graph G has the desired quadrilateral embedding of the composition graph.

Let the graph G in the problem have p vertices and q edges. From the Euler-Poincare formula a necessary condition for G[O(n)] to have a quadrilateral imbedding is 4 divides q(n^2) - 2pn. This condition is satisfied when n is even, and as noted before the embeddings exist. When n is odd the condition becomes 4 divides q - 2p. Is this necessary condition also sufficient for G[O(n)] to have a quadrilateral embedding? Note here the requirement n is at least 3, since G = G [O(1)] need not have the desired embedding.

Two meager partial results follow.

Theorem: If G has a quadrilateral imbeddding in an orientable surface and n is 1 modulo 4, then G[O(n)] also has a quadrilateral embedding.

Theorem: If G is bipartite with the property that each vertex in one of the partite sets has odd degree and each vertex in the other partite set has degree congruent to 2 modulo 4, then G[O(n)] has a quadrilateral embedding.

Submitted by: David Craft

Send comments to dan.archdeacon@uvm.edu and to craft@muskingum.edu

August, 1995