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