THE GENUS 0F CARTES'ANI PRODUCTS
OF GRAPHS

Thesis for the Degree of Ph. D.
MICHIGAN STATE UNIVERSITY
ARTHUR THOMAS WHITE II
1969

 

This is to certify that the

thesis entitled

THE GENUS OF CARTESIAN PRODUCTS

OF GRAPHS

presented by

Arthur Thomas White II

has been accepted towards fulfillment
of the requirements for

Ph.D. degree inmics

£%.7ZM'W

 

Major professor

Date July 25, 1969

 

0-169

    
 
 

3 Michigan State
you? Unive- Sit)’

 

—\

- assume av. 7

1; none a sous-

' ‘% nut-nay mum-c .

 

ABSTRACT
THE GENUS OF CARTESIAN PRODUCTS OF GRAPES

By

Arthur Thomas White II

A graph G is said to have genus n if G can be imbedded in a
compact orientable 2-manifold of genus n, where n is minimal. In
1968 Ringel and Youngs completed the determination of the genus of
the complete graph on p vertices, and by doing so solved the long-
standing Heawood map-coloring problem. There are very few other
families of graphs for which the genus is known. The main purpose
of this thesis is to determine the genus for several infinite
families of graphs.

The general method is to establish a lower bound for the genus
of a given graph, usually by using a form of the Euler formula, and
then to construct an imbedding of the graph that attains the lower
bound. The construction often employs Edmonds' permutation technique.
The structure of the cartesian product of two graphs suggests, in
certain cases, a form that the desired construction might take.

The first three chapters of this thesis introduce the subject,
define basic terms and notation, and survey known results concerning
genus problems in graph theory. In Chapter 4 upper and lower bounds

for the genus of the cartesian product G sz in terms of the genera

1
of G1 and G2 are developed, and asymptotic results are established
for the cases where G1 and G2 are both regular complete k-partite

graphs.

Arthur Thomas White II

In Chapter 5 some general results are presented in connection
with the genus of cartesian products of bipartite graphs. The
techniques developed here are applied in Chapters 6 and 7, which
contain some of the main results of this thesis.

In Chapter 6 the genus of the cartesian product of the complete
bipartite graph K2m,2m with itself is computed to be
Y(K2m,2m¥K2m,2m) = l + 8m2(m-l). As an extension of this result, let

(S) = . . (s)
Q1 Ks,s and recur81vely define Qn
it is shown that y(Q§S)) = l + 2n-33n(ns-4), for 3 even and n any

= Q(S)xK for n 2 2. Then
n-l 3,3

1 or 3 and n 2 2.

natural number, or for 3
Repeated cartesian products of certain cycles and paths are
taken in Chapter 7, and the corresponding genus formulae are developed.

For example, with G = C and G for n 2 2, where mi 2 2

1 2m n " Gn-lxc2m
1 n n_2 n
for i = 1, ..,n, it is shown that: v(Gn) = 1 + 2 (n-2) H mi.
i=1
Complete tripartite graphs are investigated in Chapter 8, and

 

it is shown that y(Kp q r) 2 (p-Zléq+r-2€} , where p 2 q 2 r, and

that equality holds if q+r s 6. It is also shown that
- Lam-22 (n- 1)
) - 2

Y<Kmn n n , for all natural numbers m and n.
3 3

THE GENUS OF CARTESIAN PRODUCTS OF GRAPHS

By

Arthur Thomas White II

A THESIS
Submitted to
Michigan State University

in partial fulfillment of the requirements
for the degree of

DOCTOR OF PHILOSOPHY

Department of Mathematics

1969

For Liz,
Mom and Dad,

and Mom and Dad Siber

ii

ACKNOWLEDGMENTS

I wish to thank Professor E. A. Nordhaus, whose inspiration,
guidance, and timely suggestions have been invaluable throughout the
preparation of this thesis. For the time which he has spent with me
and for the appreciation of graph theory which he has given me, I
am very grateful.

My gratitude goes also to Professors E. M. Palmer and B. M.
Stewart for the many discussions I have had with them and for their
helpful advice.

I would also like to thank Professors P. H. Doyle, F. Harary,
M. Hestenes, L. M. Kelly, J. R. Kinney, and J. J. Seidel for their
interest in this thesis.

This research was supported in part by National Science

Foundation Grant GZ 1222.

iii

TABLE OF CONTENTS

Chapter

1. Introduction ..........................................
2. Definitions and Notation ..............................
3. A Survey of Known Results .............................

4. Elementary Results on the Genus of Cartesian Products

of Graphs
5. The Genus

6. The Genus

Graphs ...

7. The Genus

8. The Genus

Bibliography ..............................................

.............................................

of Cartesian Products of Bipartite Graphs ...

of Cartesian Products of Complete Bipartite

of Cartesian Products of Cycles and Paths ...

of Complete Tripartite Graphs ...............

iv

17

34

38

47

55

73

LIST OF FIGURES

Figure Page
3.1 A planar graph imbedded in the torus ................ 8
3.2 A 2-cell imbedding of K5 in 32 ...................... 12
3.3 Non-intersecting edges on a handle .................. 12
4.1 An imbedding of C4xC6 in the torus .................. 19
4.2 An imbedding of P6xP8 in the plane .............. .... 19
4.3 A tube carrying m non-intersecting edges ............ 21
4.4 Identifying two vertices ............................ 29
4.5 Two vertices identified within a face ............... 31
7.1 Selecting faces for mn+1 even ....................... 52
7.2 Selecting faces for mn+1 odd ........................ 52
8.1 An imbedding of Kp,l,l in the plane ................. 59

CHAPTER 1

INTRODUCTION

A famous unsolved problem in the literature of mathematics is
the four color conjecture, which states that four colors will suffice
to color the countries of any map on a sphere. It is not difficult
to show that five colors are sufficient, but whether five colors are
necessary is not known. One of the oddities of mathematics is that
the corresponding coloring question has been completely answered for
spheres with y handles, for all positive integral values of y.

In 1890 Heawood [11] proved that the chromatic number X(Sv)

of a sphere S with y handles satisfies the inequality
Y

[7 +,/1 + 48v]
2 ’

X(Sv) s

where v > O and [x] denotes the greatest integer less than or equal
to x. The Heawood map-coloring conjecture was that equality always
holds. In 1968 Ringel and Youngs [21] settled this long-standing
conjecture in the affirmative by establishing an equivalent formula-
tion in terms of the genus of the complete graph Kp with p vertices.
To see the connection between these two problems, note that the dual
of an imbedding of K.p on the surface of a sphere with v handles is a
map in which each of the p countries shares a border with each of the
other countries, so that x(SY) 2 p.

Despite the intuitive appeal of the concept of the genus of a

graph and its application to coloring problems such as those mentioned
1

above, there are very few non-trivial families of graphs for which the
genus is known. The main purpose of this thesis is to extend the
number of these families for which the genus is precisely determined.

Definitions of terms which are basic to the study of genus
problems in graph theory are given in Chapter 2, together with much
of the notation that will be employed. In Chapter 3 a brief survey
of known results on the genus of graphs is presented.

Several elementary results are presented in Chapter 4,
particularly those pertaining to the genus of cartesian products of
graphs. Upper and lower bounds are established for the genus of the
cartesian product Gle2 in terms of the genera of G and G .

1 2

Asymptotic results are developed for the cases where G1 and G2 are
both regular complete k-partite graphs.
In Chapter 5 some general results concerning the genus of
cartesian products of bipartite graphs are presented. In Chapters
6 and 7 some of the main results of this thesis are developed. In
Chapter 6 the genus of cartesian products of complete bipartite
graphs is studied. The genera of cartesian products of cycles and
paths are treated in Chapter 7. For several infinite families of
graphs in each of these chapters, the genus is completely determined.
In Chapter 8 the genus of the complete tripartite graph Kp,q,r
is investigated. A lower bound is established, and it is shown

that the lower bound is attained for some Special cases involving

infinite families of complete tripartite graphs.

CHAPTER 2

DEFINITIONS AND NOTATION

In this chapter we define some of the terms which are
fundamental to the study of genus problems in graph theory. We also
present some of the notation that will be employed throughout this
thesis.

A gggph G is a set of vertices V(G) and a set E(G) of un-
ordered pairs of vertices called gdggs. If the elements of E(G) are

ordered pairs, G is called a directed graph. For vertices a and b

 

in V(G), (a,b) represents the corresponding edge (if present) in E(G).
If G is a directed graph, [a,b] denotes an edge directed from vertex
a to vertex b. (This notation conforms to that employed by Youngs
[27].) An edge of the type (a,a) is called a 1222. If any edge
(a,b) appears more than once in E(G), G is said to be a multigraph.
The graph G is called finite if V(G) and E(G) are both finite. In
this thesis, unless otherwise stated, all graphs are assumed to be
finite, connected, undirected, and without loops or multiple edges.
The degree of a vertex is the number of edges to which the
vertex belongs. The graph H is called a subgraph of the graph G

if V(H) C V(G) and E(H) C E(G). The complement Glof a graph G is

 

a graph having V(G) = V(G) and exactly those edges which are missing
in G. The first Betti number (or Betti numbeg) for a graph G is
defined to be E(G) = E - V +-1, where E and V denote the number of
edges and vertices of C respectively. This number is also

3

frequently called the cyclomatic number of G.

Additional terms from graph theory may be found in Harary [9].
For topological terms, one may consult Dugundji [5], Massey [13], and
Spanier [22].

A graph may be thought of as a collection of vertices, some
pairs of which are related to one another. It is when we attempt to
give a geometric realization to a graph that we encounter imbedding
problems. Any finite graph can be realized in Euclidean 3-space, but
the situation becomes more involved if we insist that the imbedding
occur in a 2-manifold.

The graph G is said to be imbedded in the 2-manifold M if the
geometric realization of G as a one-dimensional simplicial complex
is homeomorphic to a subSpace of M. Equivalently, if G is a graph
where V(G) = {v1,...,vn] and E(G) = {e1,...,em], an imbedding gf

g1

M’is a subspace C(M) of M such that
604) = u vim u u ejcm.

where
(i) v1(M),...,vn(M) are n distinct points of M.
(ii) e1(M),...,em(M) are m mutually disjoint open arcs in M.
(iii) ej(M) n vi(M) = ¢, i = l,...,n; j = 1,...,m.

(iv) if e = (

. v. ,v, ) then the Open arc e,(M) has v (M)
J J1 32 J

11

and v. (M) as end points; k = l,...,m.
2

In the above definition, an arc in M is a homeomorphic image of the
closed unit interval; an open arc is an are less its two end points,

the images of O and 1. In the remainder of this thesis, we consider

only compact, orientable 2-manifolds. We designate such a manifold
by the term "surface". If a graph G is imbedded in a surface M of
genus n but cannot be imbedded in any surface of lower genus, the
imbedding is called minimal, and the BEERE.2£.EEE gggph_is defined
to be n; we write v(G) = n. If V(G) = O, we say that G is planar.
Given an imbedding of a graph G in a surface M, each component
of the complement of G in M is called a fag; of the imbedding. If a
face is homeomorphic to the open unit disk, it is said to be a 272311.
If every face in an imbedding is a 2-cell, we say that we have a

gfcell imbedding. The total number of faces for an imbedding is

 

designated by F. For a 2-cell imbedding, Fi denotes the number of
i-sided faces, and vi denotes the number of vertices of degree i.

The imbedding is maximal if no other imbedding of the same graph has
more faces. The vertices and edges of G which belong to the boundary
of a given face are said to belong to the face itself.

Given two graphs G1 and G2, the cartesian product Gle2 has

 

for its vertex set

V(Glez) = {[u1,u2]: u1 e V(Gl), uz e V(G2)}

and for its edge set

E(GlXGZ) = {([u1,u2], [v1,v2]): u1 v1 and (u2,v2) E E(GZ)’

V

2 2 and (u1,v1) E E(G1)}o

OI'U

It is often convenient to regard Gle as being constructed by re-

2

placiJng each vertex of G with an entire copy of G1, and then joining

2

each ¢:orreSponding pair of vertices in two copies of C1 by an edge in

exactlly those cases for which the corresponding edge was present in G2-

6

2
the complete gpaph of order p and is denoted by KP. The complete

The graph with p vertices and all(p) possible edges is called

bipartite SEEEE Kp,q is the complement of the disjoint union of Kp
and Kq. Similarly, the complete tripartite graph KP: ,r is the
complement of the disjoint union of RP, Kq, and Kr' A 21213 of
length n, denoted by Cn’ is a connected regular graph having n
vertices of degree two. A pa£h_of length n, denoted by Pn’ is the

graph Cn with one edge removed.

The least integer greater than or equal to x is written as

{XI-

CHAPTER 3

A SURVEY OF KNOWN RESULTS

In this chapter the known results concerning imbedding prob-
lems in graph theory are surveyed, and the established formulae
giving genera of graphs are listed.

The 2-manifolds in which a given graph may be imbedded are
understood to be compact orientable 2-manifolds. Such manifolds

have been completely classified [13].

Classification Theorem. Compact orientable 2-manifolds are

homeomorphic to Spheres or to Spheres with handles.

For brevity, we refer to compact orientable 2-man1folds as
surfaces. The genus Y of a surface may be regarded as the number
of handles present. If the genus of a graph G is zero, the graph
may be imbedded in the surface of a sphere, and is said to be
planar. To see that such a graph may also be imbedded in the
plane, take any point in the interior of any face of an imbedding
of G in the sphere as the north pole and perform a stereographic
projection of the sphere onto the plane. The image of G is a copy
of G, now imbedded in the plane, with the image of the face con-
taining the north pole forming the exterior region. In this manner
graphs representing the five regular polyhedra, for example, may be
pictured in the plane. The familiar Euler polyhedral formula has
the following important generalization:

7

Theorem 2f Euler. Let F be the number of faces into which a Surface
of genus v is separated by a 2-ce11 imbedding of a graph G, where V
and E are the number of vertices and edges of C respectively. Then

F+V=E+2(1-v).

It is important to remember that we are assuming that G is
finite, connected, undirected, and has no loops or multiple edges.
The Euler formula is particularly useful in obtaining lower bounds
for the genera of graphs. Another useful result, due to Youngs [27],

is Stated next.

Characterization Theorem. An imbedding of a graph G is minimal if

and only if it is a maximal 2-ce11 imbedding.

A major Significance of this result is that it establishes
the applicability of the Euler formula to any minimal imbedding.
A trivial consequence of Youngs' theorem is that any imbedding of
a graph in the plane must be a 2-cell imbedding. That not all
imbeddings in surfaces of higher genus are 2-cell imbeddings is
evident from Figure 3.1, which shows a planar graph G imbedded in

the torus, or Sphere with one handle.

 

 

 

 

 

 

 

>7 ll a d
’I (1) b e (1)
a (2) d
(1) C f (1)
>; b c e f
G

Figure 3.1 A planar graph imbedded in the torus.

This imbedding has two faces, one of which (face number (2)) is a
cylinder, and hence is not a 2-ce11. The imbedding is not minimal.
Not only is the Euler theorem not applicable here, but indeed the
formula does not hold.

As another consequence of Youngs' theorem, we have the
following: if a graph G is imbedded in a surface M of genus h in
such a manner that not all the faces are 2-cells, then v(G) s h - 1.
Using his characterization theorem, Youngs also shows that if G
has a triangular imbedding (one in which every face has three Sides;
i.e. F = F3), then this imbedding must be minimal.

The following theorem of Battle, Harary, Kodama, and Youngs
[2] is also helpful in establishing lower bounds for the genera of

certain graphs:

Theorem. If G is a connected graph having k blocks B "’Bk’ then

1"

k
V(G) = 2 V(Bi)° Furthermore, in any minimal imbedding of G,
i=1

F = l - k +- E F , where F and F denote the number of faces
G i=1 Bi G B

for G and for Bi respectively.

An important corollary to the above theorem is that the genus
of a disconnected graph is the sum of the genera of its components.
The following celebrated theorem of Kuratowski [12] completely

characterizes planar graphs:

Theorem. A graph G is planar if and only if C does not contain a
subgraph isomorphic, to within vertices of degree two, to either

K5 or K3’3.

10

No such characterization of toroidal graphs (those of genus
one) is as yet known. Only recently has it been shown (by Vollmer-
haus [24]) that the class of exceptional graphs (corresponding to
KS and K3,3 in Kuratowski's theorem) is finite for any sphere with
a prescribed number of handles.

It is convenient to represent imbeddings of a graph G in the
following manner. Suppose a connected graph G has n vertices; we
write V(G) = {1,...,n}. Let V(i) = {k : (i,k) e E(G)]. Let
pi:V(i) a V(i) be a cyclic permutation of V(i) of length ni = |V(i)|,
where i = 1,...,n. The following theorem of Edmonds [7] (see also
Youngs [27]) indicates the correspondence between 2-cell imbeddings
and choices of the pi.

Theorem. Each choice (p1,...,pn) determines a 2-ce11 imbedding
C(M) of G in a compact orientable 2-manifold M, such that there is
an orientation on M which induces a cyclic ordering of the edges
(i,k) at i in which the immediate successor to (i,k) is (i,pi(k)),
i = 1,...,n. In fact, given (p1,--.,pn), there is an algorithm
which produces the determined imbedding. Conversely, given a
2-ce11 imbedding C(M) in a compact orientable 2-manifold M with

a given orientation, there is a corresponding (p1,...,pn) determin-

ing that imbedding.

Now, let D = [[a,b] : (a,b) E E(G)], and define P:D a D by:
P([a,b]) = [b,pb(a)]. Then P is a permutation on the set D of
directed edges of G (where each edge of G is associated with two

oppositely-directed directed edges), and the orbits under P

11

determine the faces of the corresponding imbedding. This result is
extremely useful, as will be seen throughout this thesis.

It then follows that the orientable genus of any connected
graph C may be effectively computed, by selecting, from the
n
Il(n

i=1
number of orbits, and hence determines the genus of the graph.

i-l)! possible permutations P, one which gives the maximal
Since a minimal imbedding must be a 2-cell imbedding, it corresponds
to some P; then by Youngs' characterization theorem, F will be
maximal for this minimal imbedding. The obvious difficulty arising
is that of selecting a suitable permutation P from the vast number
of possible permutations.

AS an illustration of these concepts, we consider an imbedding
of the complete graph K in the surface S , as shown in Figure 3.2.

5 2

Here,

V(KS) = {1,2,3,4,5}

f
[2,3,4,5] , i = 1

{1,3,4,5} , i = 2

 

V(i) = {1,2,4,5} , i = 3
{1,2,3,5} , i = a
{1,2,3,4} , i = 5

n(i) = 4, i = 1,2,3,4,5

The vertex permutations are seen to be:

p1: (2.3.4.5)
132: (1.3.4.5)
p3: (1.2.4.5)
(1.2.3.5)

p5; (1‘23334)

12

(3)

(2)

"\ I (2) p
(2) Ea CD
@319).

 

Figure 3.2 A 2-ce11 imbedding of K5 in S .

 

Figure 3.3 Non-intersecting edges on a handle.

13

This imbedding is a 2-cell imbedding, as guaranteed by Edmond's
theorem, but it is not a minimal imbedding. In the imbedding, as
shown in Figure 3.2, the two handles are only indicated at their
intersections with the surface of the sphere, which may be thought
of as curving around to meet itself in the exterior face, (3).
Handle <:), for instance, meets the Sphere in two places, as
indicated. The "missing" portion of the handle extends outward
from the plane of the page. In general, care must be taken so
that a handle carrying three or more edges reverses the order of
entrance of these edges onto the handle from one end to the other,
as Shown in Figure 3.3. This insures that the edges do not inter-
sect on the handle.

Returning to the imbedding of K5 given above, we find that the
orbits under P determine the faces of the imbedding, as required.
There are three faces, two being 5-sided and one lO-sided. Note

that, in face (2), each vertex of K is repeated and the boundary is

5

not a Simple closed curve.

(1) [1,2], [2,3], [3,4], [4,5], [5,1]

(2) [1,3], [3,2], [2,4], [4,3], [3,5], [5,4], [4,1],
[1,5], [5,2], [2,1]

(3) [1,4], [4,2], [2,5], [5,3], [3,1]

111 general, for an orbit of length k beginning with directed edge
k n n-l
‘[a,b], we mmst have P ([a,b]) = [a,b], where P = P(P ). For
5
example, for the first orbit above, since P ([1,2]) = P([5,1]) =
[1,2] ,*we have an orbit of length 5, corresponding to a S-sided

face. EaCh edge of G appears as two directed edges in D, so that

the SLnn of the orbit lengths is 2E. .This correSponds to the

14

trivial formula 2E = .231Fi° Since the above imbedding of K5 is
2-cell, we may verifylfhe Euler formula F +-V = E + 2(1 - v), where
v = 2 is the genus of the surface, and not the genus of K5. Note
that if the surface had been given the opposite orientation, with
the same permutations pi, the imbedding would have been the mirror
image of that pictured in Figure 3.2.

An orbit will henceforth be represented in the abridged form
1-2-3-4-5, instead of by the more cumbersome notation [1,2], [2,3],
[3,4], [4,5], [5,1]. Note that when we write 1-2-3-4-5 for an orbit
of length five, it is implied that p5(4) = l and p1(5) = 2.

For completeness, we next list the known genus formulae.

The BfEEEE-Qn is defined as follows: let Q1 = K2, and for n 2 2,
recursively define Qn = Qn_1xK2. In 1955, Ringel [16] Showed that
V(Qn) = 1 + 2n-3(n-4), for n 2 2. Every face in a minimal imbedding
for Qn is a quadrilateral. This formula was also established
independently by Beineke and Harary [4] in 1965.

In 1963, Auslander, Brown, and Youngs [1] produced a family
of graphs Gn for which v(Gn) = n. A graph G is said to be pfirreducible
if v(G) = n, but for any x E E(G), with Gx the graph obtained by
removing edge x from G, v(Gx) < n. In his doctoral thesis, Duke [6]
Showed that the graph Gn of Auslander, Brown, and Youngs is
n-irreducible, for n 2 2. Duke also conjectured that, for any

minimal imbedding of a graph G, F 2 2v(G) + 1. This conjecture is

valid for all genus formulae developed or listed in this thesis.

 

In 1965 Ringel [18] showed that v(Kp q) = {Craft-ll} , where
9

all faces in the minimal imbeddings produced are quadrilateral with

‘0

at most one exception. Ringel and Youngs [21] settled the Heawood

15

map-coloring conjecture in the affirmative in 1968, by showing that
V(Kp) = LE‘3]2(P-4l} . Here, all faces in a minimal imbedding are
triangular, with at most five exceptions. The proof is quite
complicated, employing various techniques such as the theory of
current graphs (see Gustin [8]) and also vortex theory (see Youngs
[25]), depending upon the residue of p modulo 12. (See also
Mayer [14].)

Ringel and Youngs [20] have recently shown that Y<Kp,p,p) =
12-1% (1)-Q , producing minimal imbeddings in which every face is a
triangle, by the means of current-graph theory.

All of the above results are obtained for orientable surfaces.

However, Youngs' characterization theorem also applies for compact

non-orientable 2-manifolds, and Youngs [28 and 29] andRingel [17]

 

have shown that §(Kp) = {(9-3%(13-41} for p 2 5 and 7‘ 7, with

P(K7) = 3, where )7 denotes the non-orientable genus of a graph.

 

2

In what follows, only the orientable genus of a graph is

Ringel [19] has also shown that 79(Kp q) = {(E'DIQ'ZL .

considered. Since many of the graphs to be studied in this thesis
are cartesian products of bipartite graphs, the following well-

1““)th theorems are frequently used.

1%. A graph is bipartite if and only if it contains no odd

Cyc les .

M. Let C be the set of all finite undirected graphs without

100138 or multiple edges, and for G and G belonging to C define

1 2

the binary operation "x" on G and G to give the cartesian product

1 2
GIXGZ. Then {C,x] is a commutative semigroup with identity K

1.

16

It is also clear that if G1 has Vi vertices and E1 edges,

1 = 1,2, then G = Gle2 has V = V1V2 and E = V1E2 +-V2E1-

Furthermore, if vertex vi has degree (11 in Gi’ i = 1,2, then
+ .
vertex [v1,v2] has degree (11 d2 in Gle2

In Theorem 5.1 of Chapter 5, we also prove that the cartesian

product of two bipartite graphs is bipartite.

CHAPTER 4

ELEMENTARY RESUITS ON THE GENUS OF CARTESIAN PRODUCTS OF GRAPHS

Given two graphs G1 and G2, with genera v(Gl) and y(G2)

reapectively, how is the genus of the cartesian product G xG

1 2
related to V(Gl) and v(G2)? In general, this appears to be a
difficult question to answer, one reason being that there are
very few graphs whose genus is known precisely. In this chapter
we compute the exact value of v(G1xGZ) for certain classes of
cartesian products of graphs and lay the foundation for the more
intricate computations of chapters 6 and 7. We also derive upper
1 and G2 are

arbitrary graphs. These bounds are sharpened for the Special case

and lower bounds for the genus of G xG2, where G

l
of the genus of Kmen. Finally, we obtain asymptotic results for
the genera of cartesian productsof regular complete k-partite graphs.
One elementary result which is frequently used in establishing
a lower bound for the genus of a graph is that the genus of a
subgraph H of a graph G cannot exceed the genus of G. To see this,
let G be minimally imbedded in a surface M of genus V(G). Remove
from this imbedding those vertices and edges of G which are not in
H. The graph H is now imbedded in the same surface M, so that
v(H) s v(G). The imbedding obtained for H need not be minimal,
nor even a 2-cell imbedding. It also follows from this observation
that if G is any graph of order p, then v(G) S v(Kp).
Another result useful in determining a lower bound for the

genus of a graph with minimum degree 5 2 3 is a variation on the
17

18

Euler formula V +-F = E + 2(1 - y). If this equation is multiplied

by 4, and the relations F = 2 Fi’ V = 2 V and

123 123 iJ
2E = 2 iFi = 2 iVi are used, we readily obtain
123 123
. l
(l) V(G) = l +-§- z (i-4)(Fi +-Vi).
123

Multiplying the Euler formula by 3 and using the same relations, we

obtain

+

adv:
O‘IH

(2) we) = 1 - z <i-3><Fi + vi).

124
This second variation is also useful in determining a lower bound
for v(G), particularly if G contains a large number of 3-cycles.
Two familiar classes of graphs are the cycles Cm, m 2 3, and
the paths Pm, m 2 2. It is relatively easy to compute the genus
of the cartesian product of two cycles or of two paths, as Shown

in Theorems 4.1 and 4.2.

Theorem 4.1. The genus of meCn is given by v(meCn) = l, for
m 2 3, n 2 3.

2322:; Since meCn can be imbedded in the torus, as Figure 4.1
illustrates for the case C4xC6,

and (2) appearing in Figure 4.1 are referred to in the proof of

then v(meCn) s l. (The numbers (1)

Theorem 7.1.) We now claim that C xC3 is not planar. It would

3
suffice to find a subgraph of C3xC3 isomorphic to within vertices

of degree two to the Kuratowski graph K3 3, but the following
9

alternative approach is offered. In the graph C the number

3XC3 ’
of 3-cycles is given by T3 = $22§_l = 6, since each vertex is in

exactly two 3-cycles, and each 3-cycle is counted three times.

It follows that F3 5 6 in any imbedding of C3xC3. If V(CBXCB) = 0,

19

then from the Euler-type formula (1) developed above, since V = V4,

we have 0 = l +-l- 2 (i-4)Fi, so that F 2 8, a contradiction.

8 3
123
Hence V(C3XC3) = 1. It follows that C3xc3 contains a Kuratowski
subgraph, and therefore so does meCn, so that V(mecn) 2 l.

Equality then follows.

Theorem 4.2. The genus of mePn is given by v(mePn) = O, for m 2 2,
n 2 2.

EEEEE‘ Figure 4.2 illustrates the case m = 8, n = 6, and it
is evident that in general Pm‘xPn is planar. (The numbers (1) and (2)

appearing in Figure 4.2 are referred to in the proof of Theorem 7.4.)

EEEEu

 

      

 

 

 

Figure 4.1 An imbedding of C4XC6 in the torus.

.EI II.
IEIEIEI

EIEIEIE m
IEIEIEI
EIEIEI II

 

Figure 4.2 An imbedding of P6xP8 in the plane.

20

We will now establish a more general result. The technique
embodied in the following theorem is employed to great advantage

throughout this thesis.

Theorem 4.3. Let a graph G be given, together with a particular

 

minimal imbedding of G having a distinguished face containing no
repeated vertices. Let G* be the graph consisting of two disjoint
copies of G, with corresponding vertices in the two copies of the
distinguished face also adjacent. Then v(G*) = 2v(G).

‘Egggf: First note that G* is a graph, since the distinguished
face has no repeated vertices, and no multiple edges have been
introduced. By the theorem of Battle, Harary, Kodama, and Youngs,
the genus of the two disjoint copies of G is given by v(ZG) = 2v(G).
Since 2G is a subgraph of G*, then 2v(G) s v(G*). Next consider
one copy of G with its imbedding specified by the permutations p1
of Edmonds' theorem and a given orientation. Imbed the second c0py
of G with the same imbedding, as Specified byW£he samggpermutntionS-pi,
in a second copy of the same surface, but with the reverse orientation.
(The second imbedding may be thought of intuitively as a mirror image
of the first.) Cut an open disk from the interiors of both c0pies
of the distinguished face, and attach the two surfaces by means of
a hollow tube, one end of which is sewn onto the boundary of each
disk. The edges needed to complete the graph G* may now be added
along this tube, as indicated in Figure 4.3. The addition of this
tube results in a surface of genus 2v(G). Although this is

intuitively clear, it may also be seen using the Euler formula.

Suppose that for G we have F +-V E + 2(1 - v). Then for G*,

2V, E* = 2E + m, where the

which is now 2-cell imbedded, V*

21

distinguished face has m sides, and F* = 2F +-m - 2. It follows

that 2F +-m - 2 +-2V = 2E +tm + 2 - 2v*, where v* is the genus of

the new surface, upon which 6* is imbedded. That is,
2F+2V=ZE+4-2y*=2E+z.-zw,

so that y* = 2v. Hence V(c*) s 2v(G), and so v(G*) = 2v(G).

 

Figure 4.3 A tube carrying m non-intersecting edges.

Reversing the orientation for the second imbedding allows the
attached tube to carry the required m edges without their intersecting
each other. We observe also that each new face is a quadrilateral.
One method for establishing the genus of a graph is to find a lower
bound for that genus, and then to construct an imbedding of the
graph for which the lower bound is attained. This method is
discussed in detail in Chapter 5. Many of the constructions to
follow in this thesis employ generalizations of the construction of
Theorem 4.3.

Before Stating an immediate corollary to Theorem 4.3, we

introduce the following definition.

22

Definition 4.1. A graph G is said to be outer-imbeddable if it has

 

a minimal imbedding with a distinguished face in which every vertex

of the graph appears exactly once.
Corollary 4.4. If G is outer-imbeddable, then v(K2xG) = 2v(G).

For examples 0f outer-imbeddable graphs, we have all cycles Cu in

the plane, K5, K6, and K393

with three handles.

in the torus, and K in the sphere

5,5

The Euler formula may also be employed to establish the

following two theorems, which we will find most useful.

Theorem 4.5. Let the graphs Gi be minimally imbedded in surfaces

 

Mi respectively, 1 = 1,2. Let the new surface M be formed by

(i = 1,...,n) between n distinct faces ofM1 and

n distinct faces of M2 reSpectively (where n S min (F1,F2)), with

tube ti carrying ei > O edges. Then v(M) = y(M1) + yflMz) + (n-l).

adding n tubes ti

Proof: Since the graphs G are minimally imbedded, the Euler

i

-F,i=l,2,

formula applies, and we have 2v(Mi) = 2 - Vi +Ei i

where, in this context, V1 and F1 give the number of vertices and
faces respectively for the minimal imbedding of graph 61' But the

new imbedding in M is also a 2-cell imbedding; hence

zvm) 2-v +E -FM

M M
n n
2 - (V1+V2) + (E1+E2 +- z ei) -(F1+F2-2n +- 2 ei)
i=1 i=1

2v(M1) + 2v(M2) - 2 + 2n.

Therefore, y(M) = v(M1) +-v(M2) + (n-l).

23

Corollary 4.6. Let G be the graph representing the 1-skeleton of

the surface M described above. Then v(G) S v(G1) +-v(G2) + (n-l).

Proof: v(G) s v(M) v(M1) + YCMZ) + (n'l)

= m1) + «62> + <n-1>.

Theorem 4.7. Let the graphs Gi be minimally imbedded in surfaces

Mi respectively, 1 = 1,...,n. Let H be a graph of order n, such

that vertex i is associated with surface Mi, and having m edges.
Let m tubes ti’ 1 = 1,...,m be attached between the surfacesMi
in correspondence with the edges of H, with no two tubes attached

within the same face, where we are assuming that F1 is at least as

large as the degree of vertex i. Let tube ti carry ei > O edges,

so as to form an imbedding of a new graph G in the new surface M.
n

Then v(G) s v(M) = 2 v(Gi) + 5(H), where B(H) is the Betti number
i=1
of the graph H.

Proof: We have Vi + F1 = Ei + 2(1 - v(Gi)), i = 1,...,n; and

n n m
V+F=E+2(1-'Y(M))- ButV= 2V..E= E.+ 2e..and
._ 1 ._ 1 ._ 1
n m 1-1 1-1 1-1
F = 2 F. - 2m +' 2 e,. Therefore,
i=11 i=11
n n m n m
2 v.+ g F. -2m-+ ze.= 2E.+ 2e.+2(1-¥(M))-
. . 1 ._. 1 . 1 , 1 . 1
1=l 1-1 1=l i=1 1=1
It follows that
n n
WM) = Z v(Gi) + (m - n + 1) = z v(Gi) +501).
i=1 i=1

It is clear that v(G) s v(M).

In Theorem 4.7, corresponding to each edge in H two surfaces

were joined by a single tube. If each "join" had been made instead

24

by several tubes running between the appropriate two surfaces, the
total effect upon the genus of the resulting surface could be
computed by combining Theorems 4.5 and 4.7 in the obvious manner.
In this case, we say that each "join" is made by a "bundle" of
tubes.

We next consider the problem mentioned earlier of estimating
v(Gle2) in terms of v(Gl) and V(GZ). A graph is said to be
‘l-factorable if it has a spanning subgraph which is regular of
degree one. Given the graphs Gi’ i = 1,2, with Vi vertices, Ei
edges, genera v(Gi), and l-factorable subgraphs H maximal with

i

respect to order, of order 2hi respectively, let

1 — V1Y(G2) + V(Gl)

2 " Vzlwl) + V(Gz)

M1 = V1(v(G2) - 1) + 131(v2 - r12) + 1

and M2 - vzmcl) - 1) + 22(v1 - hl) + 1.

We can now state the following theorem:

Theorem 4.8. The genus of the cartesian product Gle2 is bounded

 

by: Max (m1,m2) S v(G1xG2) S min (M1,M2).

Proof: (1) Consider V disjoint copies of G each with

2,

copies of vertex

1

vertex set [1,...,V2}. Add edges connecting the V1

1 so as totform a copy of G The resulting graph H is a subgraph

1.
of Gle2, and the block decomposition of H may be partitioned into
blocks of G and V copies of each block of G The theorem of

l 1
Battle, Harary, Kodama, and Youngs then applies, to give v(H) =

2.

V1v(G2) + v(G1) = m1. Clearly v(H) S v(G1xG2), as H is a subgraph

of Gle2. Interchanging the roles of G1 and G2, recalling that

25

Gle2 = G xGl, we see also that m S v(Gle2), and the left-hand

2 2

inequality of the theorem has been verified.

(ii) An imbedding (probably not minimal) of Gle2 may always
be constructed as follows: replace each vertex of G1 with a copy of
G2, minimally imbedded, and then make the required joins between
copies. Consider each join as a bundle of tubes, and count the
contribution of these bundles to the genus. By Theorem 4.7, this

is just 3(G1) = E1 - V1 +-l. Now we must count the contribution

to the genus of each bundle individually. Assuming all V copies

1

of G are minimally imbedded in surfaces of like orientation, we

2

can run no more than two edges over a given tube attached to
correSponding faces in two copies, so that these edges do not

intersect. If H is a l-factorable subgraph of G2, maximal with

2

respect to order, of order 2h h tubes will suffice for these

2’ 2

2h2 vertices. We can then join the remaining (V2 - 2h2) vertices

of G to their counterparts in a second copy over (V2 - 2h2)

2

additional tubes, each carrying one edge. By Theorem 4.5, the

contribution to the genus of this bundle is h2 +'V2 - 2h2 - l -

V2 - h2 - 1. But there are El such bundles in all. Hence,

IA

«((0le Vlv(GZ) + E1 - v + 1 + 1::le - h2 - 1)

2) l

V1(v(G2) - 1) + E1(V2 - 112) + 1

= M1.

Interchanging the roles of G1 and G2 again, we see that v(Gle2) S

M2, and the right-hand inequality of the theorem holds also.

26

The bounds in Theorem 4.8 are in general not sharp. The
above proof assumes very little about the structure of the graph

G1. For a particular C it may be possible to sharpen the

1,
upper bound considerably, by orienting the surfaces containing
copies of G2 more expeditiously, so that some or all of the tubes
added in the construction can be used to carry more than two edges.
We now turn our attention to the graphs KmeD, and attempt to
sharpen the upper bound for v(Kmen) as stated in Theorem 4.8. In

the approach that follows, we employ the concepts of line graph and

clique graph. The line graph L(G) of a given graph G has as its

 

vertex set the edges of G, and two vertices in L(G) are adjacent
if and only if the corresponding edges in G are adjacent. The

clique graph C(G) has as its vertex set the cliques of G, where a

 

cligue is a complete subgraph of G contained in no larger complete
subgraph; and two vertices of C(G) are adjacent if and only if the
corresponding cliques in G intersect. It is well-known that
L(Km,n) = Kmen [15], and this indicates a connection with the
question at hand. The following theorem gives a relationship

between clique graphs and line graphs, in certain cases.

Theorem 4.9. Let G be a graph with no triangles or vertices of

 

degree less than two. Then the graph C(L(G)) is isomorphic to G.
2522;: Let u E V(G), with degree d(u) = n 2 2. Then in L(G)
there is a complete subgraph K: associated with u. We claim that
K: is a clique in L(G). For suppose to the contrary that there is
a vertex x in L(G) adjacent to all n vertices of K2, giving (n+1)
distinct and mutually adjacent vertices in L(G). Then in G the

edge x has an end vertex in common with each of the n edges

27

associated with the vertices of K2. Since G has no triangles, and
n 2 2, the edge x must have u as one end vertex. Now, the other end
vertex of x is not one of the first n vertices, Since these are (n+1)
distinct vertices in L(G). But then d(u) 2 n + l, a contradiction.
Hence, K: is a clique in L(G).

Now, in C(L(G)), K: is replaced by a vertex, say vu. We are
ready to set up the isomorphism required by the theorem; define
e: V(G) a V(C(L(G))) by 9(u) = vu. The remarks above show that e
is well-defined.

That 9 is onto follows from the observation that {K:(u): u é V(G)]
includes every clique of L(G). To see this, note that: (i) every
vertex in L(G) is contained in some (in fact, exactly two) Kd(u)'

d

in L(G) can arise from a triangle in G, since G has no triangles;

(ii) Every edge in L(G) is in exactly one Ku(u). (iii) No triangle

hence every triangle in L(G) arises from a K configuration in G

1,3

u (iv) Any n-clique Kn in L(G),

d(u)'

n 2 4, contains a triangle, and hence, by (iii), this triangle is

and hence is in exactly one K

u . . .
in some K ° but a fourth vertex 1n Kn 15 adjacent to all three

d(u),

vertices in the triangle, and hence the edge in G this vertex

represents has u as an end vertex; that is, this fourth vertex is

u u
’ . ' d h t
1n Kd(u) It follows that Kn is a subgraph of Kd(u) an ence mus
equal K3(u), since both are cliques. So, 9 is an onto mapping.

It now follows that e is one-to-one, since the sets V(G),

{Kd(u): u 6 V(G)}, the set of all cliques of L(G), and V(C(L(G)))

all have the same cardinality. We have only to Show that adjacency
is preserved. Suppose (u,w) E E(G); then (u,w) E V(L(G)) and

hence (u,w) E Ku

d(u) O K:(w)' It follows that (vu, vw) e E(C(L(G))).

28
Conversely, let (vu, vw) E E(C(L(G))), so that in L(G) there is a

d
u and the other end vertex w; that is, (u,w) E E(G). This completes

u w
vertex x E K K . Then x is an ed e in G with one end vertex
(u) ‘1 d (w) g

the proof.

Corollary 4.10. Let G be a graph with no triangles or vertices of

 

degree less than two. Then C(G) = L(G) and C[C(G)] is isomorphic
to G.

Egggf: If G has no triangles or isolated vertices, then the
cliques of G are precisely the edges of G. Hence C(G) = L(G).
Now, since C(L(G)) is isomorphic to G, we have that C[C(G)] is

isomorphic to G.

 

Corollapy 4.11. If m and n are 2 2, then C(Kmen) is isomorphic

to K .
m,n

Proof: C(Kmen) = C(L(Km n)), wh1ch 1s 1somorph1c to Km n’

D 9

since K has no odd cycles, and in particular no triangles.
m,n

We can now improve the upper bound of Theorem 4.8, for the

graphs Kmen. Recall that the Betti number of the graph Km n is

given by B(Km n) = mn - (m + n) + 1.

Theorem 4.12. The genus of Kmen is bounded above by:

 

v(KmXKn) S nv(Km) + mvt'Kn) + MK!n n)~

9

Proof: Every vertex in Kmen belongs to exactly two cliques.
The graph Kmen has m n-cliques and n m-cliques, giving a total of
2mn vertices, each of which is counted twice. Since C(Kmeh) is

isomorphic to Km n’ the (m +-n) cliques of Kmen correspond to the
D

29

vertices of Km,n' This viewpoint motivates much of what follows.
Note also that each edge of 1(men is in exactly one clique.

We now form the graph G* from Kme.n by Splitting each vertex
of Km‘xKn into two new vertices. One of these new vertices has
exactly those adjacencies in G* that it had within one of the two
cliques it belonged to in Kmen; the second corresponding new
vertex has those adjacencies that it had within the second clique
it belonged to in Kmen. The graph G* has the same number of
edges as Kmeh, but twice as many vertices. We write V(G*) =
{Vij: i = 1,...,mn; j = 1,2]. Also, 6* consists exactly of m
n-cliques and n m-cliques, now all mutually disjoint. Hence, by
the theorem of Battle, Harary, Kodama, and Youngs, v(G*) =
nv(Km) + my(Kn). Consider G* to be imbedded, not on one surface
of genus v(G*), but on (n+m) surfaces, in the obvious manner.

We now regain Kmen, imbedded in one surface constructed
from these (n+m) surfaces. Instead of attaching these surfaces by
tubes as in the proof of Theorem 4.8, we extend the method of Battle,
Harary, Kodama, and Youngs. For each i, i = 1,...,mn, we identify
v11 with v12 as follows. Corresponding to vertex V1 in Kmen, we

now have vertices v , contained in cliques G

i] minimally imbedded

13

in surfaces Mij’ j = 1,2 respectively. Take an open 2-cell cij

in M. with simple closed boundary curve Jij such that

13
= o . o O a O o O 4.4.
(Cij U Jij) n Gij vij The Situation lS pictured 1n F1gure

 

 

 

v11 v12

Figure 4.4 Identifying two vertices.

3O

Ident1fy J of (Mil - C11) w1th J12 of 0&12 - 012) so that vil

2. This gives a surface Mi = (Mil-C11) U (MiZ-Ciz),

il
identifies with vi

with a 2-cell imbedding of cliques G1 and G12, sharing vertex vi.

1
We make the required mn such identifications, to regain the graph
KmXK.n from G*. Since each identification corresponds to adding a
required edge in C(Kmeh), which is isomorphic to Km,n (where we
are regarding the (m+n) surfaces we started with as the vertices of
Km n), this complete process has the effect of increasing the genus

’

of G* by exactly B(Km n). Hence we have 1(men imbedded in a

surface of genus nv(Km) + mv(Kn) + B(Km n), and the inequality of

the theorem is established.

The upper bound still may not be sharp, but it can be used to

give the following asymptotic result:

1+
Theorem 4.13. For n 2 m e, where e > O, and n tending to infinity,

 

v(Kmen) t mv(Kn).

Proof: Combining Theorems 4.8 and 4.12, we have:

max (mv(Kn) + V(Km), nv(Km) +-v(Kn)) S v(Kmen) S nv(Km) + mv(Kn) + 3(Km ).

 

,n
Divide through by mv(Kn), and recall that V(Kn) = Kn'3ién-4) .
1 v(Kmen)
Taking the limit as n a m, we have max(l, -) S lim S 1,
m new ml<Kn)
V(K xK)
so that lim —‘l‘-—“— = 1.
mv(Kn)

In the proof of Theorem 4.12, it was not required that the
construction employed give rise to a 2—cell imbedding of Kmen.
If the imbedding is 2-cell, the genus of the surface constructed

can also be computed by using the Euler formula, as in the proofs

31

of Theorems 4.5 and 4.7. The construction fails to give a 2-cell
imbedding, however, if any cycle of identifications (in Km,n) is
completed entirely within the same face wherein that cycle began.
In this event, at the stage at which the cycle is closed, the

new face formed is a cylinder. The upper bound of Theorem 4.12
can be further reduced by making the mn identifications so as to
insure the maximum number of cylinders. This is equivalent to
determining the maximum number of edge-disjoint 4-cycles in K , ,
which is F(m,n) = min ([§[%]], [%[%a]). Instead of closing a given
4-cycle by the usual identification procedure, since the first and
last vertex of the cycle are in the same face, they can be identified

within that face without affecting the genus, as indicated in

Figure 4.5.

a ~ b

Figure 4.5 Two vertices identified within a face.

In this manner, the upper bound of Theorem 4.12 can be reduced

by F(m,n):

32

Theorem 4.14. The genus of deKn is bounded above by:

 

V(Kmen) s mv(Kn) + rw(Km) + 8(Kmm) - F(m.n).

The technique of Theorem 4.12 can be applied to the general

cartesian product GleZ. We obtain the following result.

 

Theorem 4.15. Let the graph G1 have Vi vertices, i = 1,2. Then

v<clxcz> s VIN/(CZ) + V2Y(G1) + BOTH,”

This upper bound may be Sharper than that of Theorem 4.8, as

in the case of stK5; or it may not be as sharp, as in the case of

K3 3xK3 3. We can use the upper bound of Theorem 4.15 to obtain an
9 9

asymptotic expression for the genus of the cartesian product of two
regular complete k-partite graphs. Denote the regular complete

k-partite graph w1th ks vert1ces by Kk(s)” with KS = KS also

(1)

denoted by K1(s)'

1+
Theorem 4.16. For n 2 m e, where s > O, and n tending to infinity,

 

Y<Kk(m)xxk(n)) ~ ka(Kk(n)), for all natural numbers k.

Proof: The case k = 1 has been established by Theorem 4.13.

For k 2 2, we combine Theorems 4.8 and 4.15 to obtain
max(kmv(Kk(n)) + “Kuhn” mam”) + mm)»
s v(Kk(m)ka(n)) s knry(Kk(n)) + knv(Kk(m))
+ (kzmn - k(m+n) + 1).

We now divide through by kmv(K ) and take the limit as n a w.

xix/(K ) Mn)
We claim that lim -———5£9l7 = 0. To see this, note first that, by
n...» “(Khan

the Euler-type formula (2) developed at the beginning of the chapter,

33

2
k(k:l)n - 6kn + 12
V(Kkhn) 2 12

On the other hand,

Y<Kk(m)) s v(Kkm)

_. (km-3)(km-4)
’ 12

k2m2 - 7km + 24

< 12

 

1+3

It now follows that, for n 2 m , with e > 0,

nv( )
o s 11m.———EESEZT
n—m m (KR (n)
S lim n(k2m2 - 7km + 24) = 0.
n4» m(k(k~l)n2 - 6kn + 12)

The other limits involved are easily evaluated, and we have

max (1,l-) S lim V(Kk(m)XKk(nl) S 1,
11....» km Y<Kl< (11))

v( xK )
so that lim Kk(m) k(?> = 1.
new km V(Kk(n)

CHAPTER 5

THE GENUS OF CARTESIAN PRODUCTS OF BIPARTITE GRAPHS

One method for obtaining the genus of a graph is to calculate
a lower bound for the genus and then to construct an imbedding for
which the lower bound is actually attained. The structure of the
cartesian product Gle2 suggests a construction in which the graph

G1 is minimally imbedded in V2

surfaces are joined together as prescribed by the graph G

disjoint surfaces, and then these
2. For
each edge in G2, the two corresponding surfaces are joined by a

bundle of tubes which carry edges between all V corresponding

1

vertices in these two copies of G The challenge is to make these

1.
joins using the fewest possible tubes. AS noted following Theorem
4.3, an efficient use of a tube results in each new face intersecting
the tube being a quadrilateral. This suggests that we Should seek
quadrilateral imbeddings of a graph; that is, imbeddings in which
every face is a quadrilateral.

In the proof of Theorem 4.3, we gave the two surfaces we were
joining by a tube opposite orientations. It would be convenient if
every time we wished to join two surfaces with a bundle of tubes,
the two surfaces had opposite orientations. Then every tube attached
to two copies of the same face of the same minimal imbedding of G1
in the two surfaces can carry an edge for every corresponding pair
of vertices in the two faces. This construction would be an

improvement on that employed in Theorem 4.8, where no tube carried

more than two edges. This construction is possible provided that
34

35

G has no odd cycles; that is, provided that G is bipartite. Then

2 2

the V2 surfaces with their minimal imbeddings of G1 can be oriented

in accordance with the vertex set partition of V(Gz). It is then
clear that any join which must be made, corresponding to an edge of
62’ will be between surfaces of opposite orientation, as desired.

If we further require G to be bipartite, then G xG is bipartite,

l 2
as proved in Theorem 5.1 below, and a quadrilateral imbedding will

1

be minimal. To establish this, we prove the following two theorems.

Theorem 5.1. The cartesian product of two bipartite graphs is

 

bipartite.
Proof: Equivalently, we Show that if neither G1 nor G2
contains an odd cycle, then (:le2 cannot contain an odd cycle.

So, consider a cycle of length m in G xG2; then h edges of the

1

cycle are taken from one or more copies of G O S h S m; and

19

(m-h) edges join corresponding vertices of two copies of G1,

corresponding to edges in G2. Superimpose the V2 copies of G1
onto one copy of the graph G1. The (m-h) edges above disappear,
and the h edges now form a cycle in G1. Since G1 has no odd

cycles, h is even. Similarly, by superimposing the V copies of

1

G2 onto one copy of the graph G2, we see that (m-h) is even.

Hence m is even.

Let the graphsGi, i = 1,2,... be bipartite, and define the

. Then

graph Hn as follows: H and recursively Hn = H

1 = G1’ n-1XGn

Hn = Glezx...xGn, and the following corollary of Theorem 5.1 is

established by a routine application of mathematical induction:

36

Corollary 5.2. The graph Hn is bipartite.

Theorem 5.3. A quadrilateral imbedding of a bipartite graph'is a

 

minimal imbedding.

Proof: A bipartite graph has no odd cycles, and in particular

no 3-cycles. Hence in any imbedding, F3 = 0. Recall that 2E

2 iFi’ with F = 2 F1’ and that a 2-cell imbedding of a graph is
123 123
minimal when F is maximal, by the characterization theorem of Youngs.

Then if F = F

4 for a bipartite graph, the imbedding must be minimal.

The next theorem has frequent applications in Chapters 6 and 7.

Theorem 5.4. If a bipartite graph G with V vertices and E edges has

 

a quadrilateral imbedding, then y(G) = 1 +-E- - %.

Proof: By Theorem 5.3, the imbedding is minimal, and hence is

a 2-cell imbedding. The Euler-type formula

- _ .1 .
(1) we) - 1 +32 <1-4><F,+vi)
123

discussed in Chapter 4 applies. Noting that F1 = O for i f 4,

with 2E = 2 1V, and V = 2 V,, the result follows immediately.
123 1 123 1

To construct quadrilateral imbeddings for G sz, where both

1

1 and G2 are bipartite, we will follow the procedure outlined at

the beginning of the chapter. The contributions to the genus of

G

the surface which arises from this procedure are of three types:

(1) V surfaces of genus v(G1) each, with which we start our

2

construction; (11) the contribution of the tubes within each bundle;

and (iii) the contribution of the bundles taken collectively. The

37

first contribution is known once the genus of G1 is known. The
second and third contributions can be computed using Theorems 4.5
and 4.7 reSpectively.

It is intuitively clear that all the tubes required by this
construction may be added so that they do not intersect each other.
This fact is also evident from the following theorem, which may be
established by standard topological arguments; the proof is omitted.
By a ggneralized gfmanifold is meant the union of a finite collection

of compact orientable 2-manifolds in Euclidean 3-space, each of which

is exterior to any other.

Theorem 5.5. If M is a generalized 2-manifold, with C1 and C2 two

 

disjoint simple closed curves on M such that C1 is homotopic to zero

on M-C and C then there exists a

2 2 1’
topological cylinder K with bases C1 and C2 such that K.n M = C1 U C2.

is homotopic to zero on M-C

Adding tubes one at a time and applying mathematical induction,
we see that all the tubes required by the construction of this chapter
may be added without intersecting one-another.

We are now prepared to construct quadrilateral imbeddings for
certain cartesian products of bipartite graphs, and will thus be

able to determine their genus exactly.

CHAPTER 6

THE GENUS OF CARTESIAN PRODUCTS OF COMPLETE BIPARTITE GRAPHS

In this chapter we present one of the main results of this

thesis: the computation of the genus of the graph Ks ssz s for
3 9

the cases 3 = l, s = 3, and for all even 3. We then generalize
this result by taking the cartesian product of arbitrarily many

copies of KS 3 and computing the genus of the resulting graph.

The approach developed in Chapter 5 is useful in accomplishing
this.

) = (m-1)2, with F = P4 =

2m2. The particular minimal imbedding given by Ringel [18] for

Recall that, for s = 2m, Y<K2m,2m

this case is:

[j: 2m+l S j S 4m], 1 S i S 2m
V(i) =
{j: lsjszm], 2m+lSiS4m

C I O : ZIII' 2(11'2 O I I , ‘III

p19p39 3132 _] ( 19 3 )
r I O I z 4"! 4(11- 1 I) l O O 3 ZIII C 1

p231]: J ’pzm ( 9 . )

: 1 ...
p2m1>p2m+33"’9p4m_1 ( :2: 82m)

p2m+2’p2m+4"°°’p4m:
The following lemma is used to compute the genus of

K2m,2mXK2m,2m:

Lemma 6.1. For the imbedding of K m 2m given above, the set of

2

38

39

2m2 quadrilateral faces may be partitioned into 2m subsets of m
faces each so that each subset of m faces contains all 4m vertices
of the graph.

2:22;: We write out the orbits (each corresponding to a
quadrilateral face) determined by the permutation P as defined by

the permutations pi, 1 S i S 4m (see Chapter 3), given above:

(2g-1)-(2h-l)-2g-(2h~2), l S g S m; m+l.< h S 2m
(2g-1)-(2h-1)-2g-4m, 1 S g S m; h = m+l
2j-(2k-1)-(2j+l)-2k, m+l S k S 2m, 1 S j < m

2j-(2k-l)-l-2k, m+1 s k s 2m, j = m.

We now assign these 2m2 faces to parts of the partition. For
fixed 1, the m faces of part (21-1) are determined by selecting
h = m + g + i, with l S g S m, where we reduce (g + i) modulo m
and write m instead of O. The m faces of part 21 are determined by
taking k = m_+ j + i, with 1 S j S m, where we reduce (j + i)
modulo m and again write m instead of O. Letting i run between
1 and m, we obtain 2m sets of m faces each, the sets being mutually
disjoint by the manner in which they were selected. Furthermore,

each set of m faces contains all 4m vertices of the graph sz 2m'
9
We are now in a position to prove the following theorem:

Theorem 6.2. The genus of KS,SXKS,S is g1ven by Y<Ks,sXKs,s) -

 

1 + 82(8-2), if s is even or if s = l or 3.
Proof: We consider three cases:

Case 1 . For 3 = l, K xK = K xK = C4, and V(C4) = O.

For the other cases, it suffices to produce a quadrilateral

40

imbedding, as a result of Theorems 5.1 and 5.3. Then by Theorem

5.4, since V = 432 and E = 433, will follow that V(KS SxKS S) =
l + 32(5-2).
Case 11 . For 3 = 3, we use an imbedding of K3 3 for which
F = F6 = 3
[4,5,6] , i = 1,2,3
V(i) =
{1,2,3} , 1 = 4,5,6

p19p29p3: (4‘635)
134.95.136: (1.3.2)

For this imbedding, each face contains each vertex of the graph
exactly once. Designate the three faces by (1), (2), and (3). Now,

take three copies of K imbedded in this fashion, and three

3,3
additional copies imbedded with reverse orientation. Designate
the corresponding faces in the latter three copies by (l), (g),
and (3). At this stage, we have Six tori, each with a copy of
K3 3 imbedded as described by the vertex permutations given above;
9

label these tori by a, b, c; d, e, and f. To imbed K xK

- ‘- -' 3,3 3,3

must join each vertex in each of a, b, and c to its counterparts

, we

in 3, in g, and in f. To accomplish these joins, we add the
following nine tubes, each of which will carry the necessary six
edges and itself corresponds to an edge in K3,3: a(l) to QQL),
a(2) to 2(3), a(3) to 2(3); b(l) to 2(3), b(2) to 2(3), b(3) to
3(3); and c(1) to E(l), c(2) to 3(3), c(3) to 2(3). As in the
proof of Theorem 4.3, since every tube is attached at two corre-

Sponding faces of opposite orientation, all six edges that the

tube must carry may be added across it without intersecting one

41

another. (Refer to Figure 4.3, with m = 6.) As every new face thus

formed is a quadrilateral, and each hexagonal face in the original

imbedding of any copy of K3 3 has been destroyed, we have constructed
9

a quadrilateral imbedding of K3 3xK3 3.

Case (111). For 3 = 2m, imbed 4m copies of sz,2m 1n 4m

surfaces, each of genus (m-1)2, using the imbedding of Lemma 6.1.

 

We choose one of the two possible orientations for 2m of these
surfaces, and the reverse orientation for the remaining 2m surfaces.

This partition correSponds to the vertex set partition for sz 2m'
9

Between each pair of oppositely oriented surfaces, we must add 4m

edges in order to imbed K We add these 4m edges over

2m,2m3K2m,2m

m tubes, each carrying four edges. There are 2m such joins that
must be made from each surface. Lemma 6.1 establishes that Ringel's

imbedding for the COpy of K at each surface is ideally suited

2m,2m

for this purpose. We need only check that we can match corresponding
parts of the face partitions appropriately. At copy j, 1 S j S 2m,

of minimally imbedded with common orientation, match part i

K2m,2m
of the face partition with part i in copy 1 + i,‘1 S j +-i S 32

(mod 2m) of K minimally imbedded with the opposite orientation.

2m,2m

If j + i = j'+i' with i = 1', then j.=‘j', so that each part of each

 

partition has exactly one tube attached at each face in that part.
As in case (ii), each new face is a quadrilateral. We have con-

structed a quadrilateral imbedding of K completing

2m,2m3K2m,2m’
the proof.

For the above construction, using Theorems 4.5 and 4.7, we
can compute the genus of the resulting surface directly, without

recourse to the Euler-type formula of Theorem 5.4. The contributions

42

to the genus are of three types: (1) 4mv(K ) = 4m(m-l)2,
2m,2m

representing the collective genera of the surfaces with which we

began our construction; (ii) 4m2(m-1), representing an increase

of (m-l) in the genus for each of the 4m2 joins, due to the

addition of m tubes; and (iii) a(sz 2m) = (2m-1)2, representing
9

the contributions of the bundles taken collectively. Adding, we

see that

l + (2m)2(2m-2)

Y(KZm,2m‘XKZm,2m)

l + 32(5-2), where s = 2m.

This computation provides an unusually intuitive connection between
the formula for the genus and the realization of the imbedding in

Euclidean 3-space.

We can use Theorem 6.2 to prove the following corollary, which

is actually a generalization of this theorem:

Corollary 6.3. The genus of K ) =

 

s is given by v(K

2m,2mXKr, 2m,2m8Kr,s

1 + m[(m-2)(r+s) + rs], if r S 2m and S S 2m.

Proof: Imbed K as in the proof of Theorem 6.2,

2m,2mXK2m,2m

with F = F4. Remove (4m - (r+s)) surfaces containing copies of

sz 2m’ together with all tubes and edges issuing from these surfaces,
9

so as to leave an imbedding of K xK . This imbedding is also
2m,2m r,s

quadrilateral, since each copy of K was initially imbedded

2m,2m

quadrilaterally, and the removal of any tube re-introduces only

K is a

quadrilateral faces. Hence this imbedding of K x
2m,2m r,s

minimal imbedding; and by Theorem 5.4, with V = 4m(r+s) and E =

2
4m (r+s) + 4mrs, we obtain

43

2
v(K2m,2mXKr S) = l + (m (r+s) + mrs) - 2m(r+s)

9

= 1 + m[(m-2)(r+s) + rs)].
From Corollary 6.3, we can readily deduce the following:

Corollary 6.4. The genus of K is given by y(K

2m, ZmXKZn , 2n 2m, 2mXK2n, 2n)

= 1 +~4mn(m + n - 2), for all positive integers m and n.

Now we define a class of graphs which generalize the n-cube

, f : (S) = . (S) =
Qn as ollows let Q1 Ks,s’ and recursively define Qn
Q(s)xK for n 2 2. The constructions of Theorem 6.2 can be

n-l s,s’

extended, as developed in the next three theorems.

(2m) 2n-2 n
m
n

Theorem 6.5. v(Q ) = l +,2 (mn-2)

(2m)

Proof: By Corollary 5.2, Qn

is a bipartite graph. We
2
:Zm) , and compute v(Q( m))

n
using Theorem 5.4. It is clear that V = 4mm? for QéZm).

produce a quadrilateral imbedding for Q
We
establish the values of E and F, Showing that F = F4, by mathematical

induction. Let the statement S(n) be as follows: There is an

- +1
imbedding of qéZm) with E = n22nmn+1 and F = F4 = n22n 1mn ,
including 2m mutually disjoint sets of 22n-2mn mutually vertex-

n n
disjoint quadrilateral faces each, each set containing all 4 m

(2m)

n We claim that S(n) is true for all natural

vertices of Q
numbers n. That S(l) is true follows immediately from Ringel's

imbedding of K2m,2m and Lemma 6.1.

Now, assuming S(n) to be true, we establish S(n+l), for n 2 1.

So, consider a large copy of K m 2m’ each vertex of which is
9

2

replaced with a small copy of Q§2m) imbedded as described by S(n)

44

and with respective orientations determined by the vertex set

partition for K Label the 2m copies of one orientation by

2m,2m°

j, 1 S j S 2m, and the 2m copies of Opposite orientation by

i, 3.5 1.S 39, Now, by the induction hypothesis, each copy of
(2m)
Qn

has 2m sets of faces available, one set for each of the 2m

joins that must be made from that copy. Furthermore, each set

(2m)

contains each vertex of the graph Qn

exactly once. As in the
proof of Theorem 6.2, at copy j, l S j S 2m, match set i with
set i_in copy j_:_i, l S j_:_i S gm (mod 2m). For each matching
a tube carrying four edges is attached between each pair of
corresponding quadrilateral faces. In this manner the required

4m2 joins are completed, so that we have a quadrilateral imbedding
(2m)

0f Qn+1 °

(2m)

Now, for fixed j, pair off copy 1 of Qn

with copy 1 + j,

where 1.3 i + j S gm (mod 2m). For each such pairing, with copy

i joined to c0py i + j by 22n-2mn tubes, we have (for fixed j and

i = 1,...,2m) a total of 4(22n-2)mn(2m) = 22n+1mn+1

2n-1 n+1
m

quadrilateral

faces on 2 tubes. For each tube, select one pair of

opposite faces. The 22nmn+l faces thus selected are mutually
n+1 n+1 (2m)
m

n+1 . Now

vertex-disjoint and contain all 4 vertices of Q
letting j vary between 1 and 2m, we obtain 2m mutually disjoint

such sets of quadrilateral faces, as claimed by S(n+l).

+1 +1
The imbedding of Qéii) we have obtained has E(n ) = Fin ),
since P(n) = Fin) and the attaching of each new tube with the

four edges it carries eliminates two quadrilaterals and introduces

F(n+1) = We)

four new quadrilaterals. Now, + AF, where AF is
twice the number of tubes added at this stage. But the number of

n n
tubes added is (4m2)£&—%-l = 4nmn+2, where 4m2 is the number of

45

edges in sz 2m (corresponding to the number of joins we made),
9
4mm? is the number of edges per join, and there are four edges per

tube. Hence

F(n+1) = 4m(n22n-1mn+1) + 2(4n mn+2)
= (n+1)22n+lmn+2.
Also,
E(n+1) = 4mE(n + 4m 2v(n)
= 4m (n 22nmn+l) + 4m2(4nmn)
= (n+1)22n+2mn+2.

We have established that S(n+l) follows from S(n), for all
n 2 1. Thus S(n) holds, for all natural numbers n. Now, by
Theorem 5.4,

2n n+1 n
. (2m) = n2 m _ 4 m
YiQn ) 1 +‘-1;-- 2

n

 

= 1 + 22n‘2m“(mn-2).

AS with the construction of Theorem 6.2, we can also compute

the genus of Q(? T) directly, given the genus of Q(2m). We have:
2m 2m)-1n
YQrE-I-l) = 4mv(Qn ( ) + 4m2 (4n Inn -1) + 3(K2m 2m)
= 4m(l + 22m- 2 mn(mn- -2)) + 4m 2(4 n 1mn-l) +-(4m2 -4m+l)
= 1 +2 22n Mn+l[ (n +1) 2]

We have also the following generalization of Theorem 6.5, the

proof of which is analogous to that of Corollary 6.3:

Corollary 6.6. The genus of Q<2m)xK Kr t is given by V(Qézm)xKr t) =
1+ 22n 2 mn[(r+t)(mn- -2) + rt], for r S 2m and t S 2m.

46

In Theorem 6.5, it was convenient to consider Ks s for 5 even,
3

since K has F = F in its minimal imbedding. The arguments of
2m,2m 4

Theorem 6.5, with minor modifications, apply also to the cases

3 = 1 and s = 3. We can therefore state:

 

Theorem 6.7. The genus of Qés) is given by V(Q;S)) = 1 + 2n-33n(ns-4),
for 8 even and any positive integer n, or for s = l or 3 and n 2 2.

The genus formula given in Theorem 6.7 includes as two of
2 . n-3
' == - = + .-
its special cases V(KZm,2m) (m l) and V(Qn) 1 2 (n 4),

two of the familiar results in the literature.

(8)

n+1 employed in

The constructions of minimal imbeddings for Q

the proof of Theorem 6.7 used only half of the available faces on
(8)

each tube in the given minimal imbedding of Qn , for n 2 2.

Using every face on every tube, a similar argument can be employed
to construct a quadrilateral imbedding for the following graph:

let G = K , and recursively define G = G
l 8,3 n
t = 2n-zs, and n 2 2. Noting that, for Gn”
ngn-lz + 1

V00 = 2 2 sn,

,xK where
n-i t,t’

while
(n+21(n-l)
(n) 2

+
E = 2 sn 1

-1
(using the fact that Gn is regular of degree d(u) 2n 3), we use

Theorem 5.4 to compute the following result:

nSn-lz
n-3

+ 2 s“(2 s-l),

I
..a

Theorem 6.8. The genus of GH is given by V(Gn) ‘

or 3 and n 2 2.

H
H

for 3 even and any positive integer n, or for s

CHAPTER 7

THE GENUS OF CARTESIAN PRODUCTS OF CYCLES AND PATHS

Every path is a bipartite graph, as are all cycles of even
length. We have computed the genus of the cartesian product of
two cycles, or of two paths, in Chapter 4. In this chapter we
take repeated cartesian products of certain of these graphs and
compute their genera. The approach is similar to that employed
in Chapter 6.

Define the graph Gn as follows: let G = C , the cycle on

1 2m1
2m vertices, and recursively define G = G xC , for n 2 2,
l n n-l 2mn
where we require each mi to be-2 2. Let M(n) denote H mi. The
i=1

following genus formula contains (n+1) parameters:

 

Theorem 7.1. The genus of Cu is given by V(Gn) = l + 2n-2(n-2)M(n),
for n 2 2.

2529;; By Corollary 5.2, Gn is a bipartite graph. We produce
a quadrilateral imbedding for Gn’ and compute v(Gn) using Theorem
5.4. For Gn’ V(n) = 2nM(n); and since Gn is regular of degree 2n,
it is a simple matter to compute E(n) = ZnnM(n). Now, let the

statement S(n) be: There is an imbedding of Gn for which F = F4
nZn-lm‘n), including two disjoint sets of Zn-ZM‘H) mutually vertex-

. . nM(n)
disjoint quadrilateral faces each, both sets containing all 2
vertices of G“. We claim that S(n) is true for all n 2 2. We
verify this by mathematical induction.

47

48

That S(Z) is true is apparent from Figure 4.1, with the faces
designated by (1) making up one set and those designated by (2)
making up the other. Now we assume S(n) to be true and establish

S(n+l), for n 2 2. For the graph Gn+1’ we start with 2mn copies

+l
of Gn’ minimally imbedded as described by S(n). We partition the

copies of one orientation and m

corres ondin surfaces into m
P 8 n+1

n+1

copies of the reverse orientation, corresponding to the vertex set

partition of C From each copy, two joins must be made, both

2mn+1

to c0pies of opposite orientation. From the statement S(n), it is

. n-ZMOI)
clear that these two jOins can be made, each one over 2 tubes
carrying four edges each. Each new face formed is a quadrilateral.

In this fashion the required 2mn+1 jOins can be made to imbed Gn+1’

with F = F4. Now form one set of faces by selecting opposite quad-

rilaterals from each tube added in alternate joins in this construction.
Form the second set by selecting the remaining quadrilaterals on the

same tubes. It is clear that the two sets of faces thus selected are

disjoint, and that each contains (2)(mn+1) (2““2M(“)) = zn'gimfl)

mutually vertex-disjoint quadrilaterals; both sets contain all

n+1M(n+1) (n+1) =

(n)
2 vertices of Gn+1° Furthermore, F 2mh+1F + AF,

= n-2 (n) . .
where AF (2mn+1)(2 M )(2), where 2mn+1 JOlnS have been made,
with 2n-2M(n) tubes per join, and a net increase in F of 2 per tube.

Hence,

F(n+1) = 2mn+1(n2“']}4(“)) + 2“M(n+1)

(n+1) 2‘54 (n+1) ,

and we have established that S(n+l) follows from S(n). Therefore,

S(n) holds, for all n 2 2. We can now compute:

II
....I
+

I

“6.9 ‘7.— 7—

1 + 2“'2(n-2)M(“).

For the special case where mi = m, i = 1,...,n, we have

(n) n

M = m , and:

(m)

n ) = 1 + 2n’2(n-2)m“.

Corollary 7.2. The genus of Gém) is given by y(G

Furthermore, if m = 2 in the above formula, since C4 = K2 2 =
G<2)

KZXKZ’ is the 2n-cube, and we obtain the familiar result:

Corollary 7.3. V(an) = l + 22n-2(n-2).

 

We now turn our attention from cycles to paths. Let H1 = Pm ,
1

vertices, and recursively define Hn = H xP , for

a ath on m
p n-l Inn

1

n 2 2. All paths are bipartite graphs, but we nevertheless restrict

m , m . and m to be even in the theorem to follow. The complexity

1 2’ 3

of this genus formula in comparison with that of Theorem 7.1 is
largely due to the fact that the graphs Gn are regular, whereas the
graphs Hn are not (unless mi = 2, for all i = 1,...,n). Since
Theorem 4.2 covers the case n = 2, we consider here only n 2 3. We

(n) n
again let M = H m .

Mon)

 

n
1

Theorem 7.4. The genus of H is given by v(H ) = 1 + (n-Z- E ——9,

n “ i=1mi

for n 2 3 and m1, m2, and m3 all even,

Proof: By Corollary 5.2, fin is a bipartite graph. We construct
a quadrilateral imbedding for Ru, and compute V(Hn) using Theorem 5.4.
For Hn’ V(n) = M(n). Now, let the statement S(n) be: There is an

n
(n) 2 fi—, including

imbedding of an for which F = F = EM(“) - 1M
i=1 i

4 2 2

50

two disjoint sets of %M(n) mutually vertex-disjoint quadrilateral

(n)

faces each, both sets containing all M vertices of Hn; furthermore,

for Hn’ E(n) = nM(n) - M(n) ; 173 We claim that S(n) is true for all
n 2 3. We verify this by matéematical induction.

To see that S(3) is true, refer to Figure 4.2, which shows that
y(P6xP8) = 0. Every face but the exterior face is a quadrilateral
for this imbedding. We see that two joins may be made at each copy
of Pmlem2 in general, provided m1 and m2 are both even. One join
employs the faces designated by (l), and the other join uses the
faces designated by (2), as in Figure 4.2. Provided m3 is even also,
we can arrange the two end c0pies of Pmlem2 so that the faces (2),
including the exterior face, are employed in the single join that

must be made from each end copy. Partition the m3 copies of Pm me

m3 m3 1 2
into 2— copies of one orientation and 2— copies of the other

orientation, with the two end copies in different parts of this
partition (corresponding to the vertex set partition of Fm .) The
3
graph H = P xP xP thus has a quadrilateral imbedding, since a
3 m1 m2 m3

tube attached between two oppositely oriented copies of the exterior
face (2) replaces those two faces of 2(m1+m2-2) sides each with
2(m1+m2-2) quadrilaterals, once the required edges are added over the

tube. Now,

E(Z) = (ml-l)m2 + (m2-1)m1
= 2m1m2 ' m1 ' m2”
so that
3(3) = m3E(2) + (m3-1)V(2)
= 3m1m2m3 ‘ m1m3 ‘ m2m3 ’ m1m2°

51

3 .
Also, F( ) = m3F(2) +-AF, where AF is the increase in faces accounted
for by the tubes we have added. This increase is of two types,
corresponding to tubes attached within faces designated by (l) and

to tubes attached within faces designated by (2). We have:

(3) _ . . _m_3_ . flmz
F m [on1 1><m,-1> + l] + 2c, - m, E”) +

m m

m
:3 1. 2
5-{2(§— - 1) (2— - 1) + 2(m1 + m2 - 3)]

2111mm _ 12_ 13_ 23
2123 2 2 2

Furthermore, consider the set of faces obtained by taking, from
each tube joining faces designated by (2), every second face. These
faces are mutually vertex-disjoint, and contain all mlmzm3 vertices
of H3. Now, form a second set of faces consisting of the remaining
faces on the tubes joining faces designated by (2). These faces are
also mutually vertex-disjoint, and contain all mlmzm3 vertices of
H3. Moreover, the two sets of faces we have selected are clearly
disjoint. Therefore, 8(3) is true.

Now we assume S(n) to be true, and establish S(n+l), for n 2 3.

Given the graph Hn+ , we give the m

copies of H minimal imbeddings
n+1 n

as described by S(n), with orientation as determined by the vertex

set partition of Pm . It is clear that we can make the required
n+1
(mn+1 - 1) joins so as to obtain a quadrilateral imbedding for Hn+1°
Wehmm
(n+1) _ (n) . (n)
E - mn+1E + (mn+l 1)V
= m, (nM(n)— Mm)n z —) + (mn - 1)M(“)
n+1 m
i= -1 1
+1
= (n+1)M(n+l) Mm +1)“:

. "1.
i=1 i

52

(n+1) = m F(n)

A1
so, F n+1

+ AF, where AF = (mn+1 - 1)<§M(“))(2).

where mn+1 - l is the number of joins, %M(n) is the number of tubes

per join, and there is a net increase in F of two for each tube.

We have

(n+1) _ (n) (n) n 1_ (n+1) (n)
F — mn+1(%M ’ i“ 2 ) +'%M ' %M

i=1 mi
_ gn+12 (n+1) ;M(n+1)“+1 1
— 2 M - 2 121 E; .

To complete the verification of S(n+l), we must find two disjoint

(n+1)
M w 1 o a o v
sets of -—4_—— mutually vertex-diSJOint quadrilateral faces each,
' ' (n+1) v
both sets containing all M vertices of Hn+l' We have two cases
to consider:
Case i . If m is even we choose opposite faces on each

n+1

tube of alternate joins to form one set, and the remaining faces on

the same tubes to form the second set, as indicated in Figure 7.1.

 

Figure 7.1 Selecting faces for mn+1 even.

Case (ii). If mn+1 is odd, we make our selection as indicated
in Figure 7.2, using at each end copy of Hn the remaining set of
%M(n) mutually vertex-disjoint quadrilaterals. As in Figure 7.1,
an arrow at a join indicates that opposite faces on each tube of

the join have been selected.

 

Figure 7.2 Selecting faces for mn+1 odd.

53

We have shown that S(n+l) follows from S(n), and hence that
S(n) holds for all n 2 3. It only remains to compute the genus of

H . But by Theorem 5.4,

 

n
_ l (n) (n>“i_ _ (n)
V(Hn) - 1 + 4(nM - M .§.m ) %M
1-1 1
(n) n 1
- 1 + (n - 2 - 2 ——).
i=lmi

Since the operation of taking the cartesian product is
commutative, Theorem 7.4 can be applied if any three or more of the

m1 are even. Elementary probability considerations show that this

n2 + n+2

2n+1

For n > 5, this probability will be less than one half.

fails to happen in only of the possible cases, for fixed n.

For the special case where m1 = m, i — 1,...,n, for m even,

we have:

 

 

. , (m) . . (U0 _
Corollary 7.5. The genus of the graph Hn is given by y(Hn ) -
n-l
l + m (mn - 2m - n), for m any even positive integer.

4

(2)

n

Futhermore, if m = 2 in the above formula, H is the n-cube,

since P2 = K2, and we have the familiar result:

 

-3
Corollary 7.6. v(Qn) = 1 + 2n (n-4).

We have now generalized the genus of the n-cube in three

different directions: in Theorem 6.7, regarding K1 1 as K2; in
Theorem 7.1, regarding C4 as KZXK2 to obtain the genus of the 2n-cube,
and in Theorem 7.4, regarding P2 as K2.

We have thus far studied the genus of cartesian products of

bipartite graphs and in particular of complete bipartite graphs,

54

even cycles, and paths. The techniques we have developed can also
be applied to cartesian products of certain combinations of these
graphs. The following theorems are a sample of results in this

direction. The proofs, being similar to those already given, are

omitted.

Theorem 7.7. The genus of the graph KZXPZmXCZn is given by:

v(K2xP2me2n) = l + n(m-l), for n 2 2.

Theorem 7.8. The genus of the graph KZXP2 MXCZ xK4 4 is given by:

v(K2me xC xK = 1 + 8n(5m-l), for n 2 2.

2n 4,4)

Theorem 7.9. The genus of the graph C2 me2 nXK4 4 is given by:

= l l , d .
v(02me2nxK4,4) + 6mn. for m 2 2 an n 2 2

 

CHAPTER 8

THE GENUS OF COMPLETE TRIPARTITE GRAPHS

Since the genus has been determined for the complete graphs
KP and for the complete bipartite graphs Kp,q’ it seems appropriate
to investigate next the genus of the complete tripartite graphs
This problem appears to be very difficult, and in this

Kp.q.r'
chapter we will be content to establish a lower bound for Y<Kp,q,r)
and to show that the lower bound is attained in certain special
cases, each of which includes infinitely many graphs of this
family.

The graph Kp,q,r has (p + q + r) vertices, which are
partitioned into three sets P, Q, and R, containing p, q, and r
vertices reSpectively. We assume throughout this chapter that
p 2 q 2 r 2 l. The edges of Kp,q,r are precisely those edges which
join a vertex in one of the three sets to a vertex in one of the

other two sets. In order to distinguish the three types of edges

which occur, we make the following definition:

Definition 8.;. An edge of the graph KP q r WhiCh joins a vertex
3 9
in set R with a vertex in set Q is called an edge of type 1.

Similarly, an edge joining sets R and P is called an edge of

type II, and one joining sets Q and P an edge of type III.

Since there are qr edges of type I, pr edges of type II, and

pq edges of type III, the total number of edges is E = qr + pr + pq.
55

56

Lower bounds for genus formulae are ordinarily obtained by
the use of the Euler formula and certain properties of the graph
in question. Theorem 8.1, which follows, can be established in
this way, but a simpler proof is presented which used Ringel's

result for the genus of complete bipartite graphs.

Theorem 8.1. The genus of the graph KP r is bounded below by:

sq:
(13-2) (q+r-2)
Ya<P3Qar> 2{ 4 } .

Proof: Consider any minimal imbedding of Kp q r in a surface
3 3

M. By the removal of all edges of type I from this imbedding, we

 

obtain an imbedding of K in the same surface M. Hence

V(K ) = film) 2 V(Kp q+r) = {(1)-22941-21} , by Ringel's formula

 

P:Q:r

for the genus of complete bipartite graphs.

Much of the remainder of this chapter is devoted to showing
that equality holds in Theorem 8.1 when q + r s 6, and we conjecture

that it holds for all complete tripartite graphs.

 

Conjecture. Y<Kp,q,r) = {FF-2)49+T-2{} .

The result of Ringel and Youngs that v(Kp p p) = (P‘1)§P‘2)
D 9

is seen to be consistent with this conjecture. We will also show

that y(K ) = (mn-Z;(n-ll, which likewise agrees with this

mn,n,n
conjecture. The other cases where q + r > 6 remain open.

To show that equality holds when q +'r s 6, it is sufficient
to construct an imbedding of K in a surface of genus

P,Q:r
{?p-2)£q+r-2%} , so that Y<Kp,q,r) S {FP‘2)éq+T‘2i} . The

following lemmas will assist us in investigating the face

 

 

57

distributions of such an imbedding.

Lemma 8.2. In an imbeddin of K , F S 2 r.
y g 139(13): 3 q
Proof: Any 3-cycle in K q must be composed of one edge of
3 3

each of the three types, since otherwise two vertices in the same
vertex set would be adjacent, a contradiction. Hence any triangle
in an imbedding of this graph contains one edge of each type, and
in particular an edge of type I. But there are only qr edges of
type I, and each edge appears in at most two faces in any imbedding

of the graph. Hence F3 s 2qr.

= 2qr, then F = O,

3

Lemma 8.3. If an imbedding of Kp q r has F 2i+l

3 3

for i = 2,3,...

2129:: If F3 = 2qr, the qr edges of type I each appear in
two triangular faces. Any other face must then include only edges
of type II or of type III. Since the vertices of Kp,q,r are
partitioned into three sets P, Q, and R of p, q, and r vertices
respectively, the boundary of any non-triangular face is a subgraph
of the bipartite graph Kp,q+r’ which has its vertex set partitioned
into sets P and Q U R. Any such subgraph is itself a bipartite

graph and hence cannot contain any odd cycle. We observe that a
face could contain a given vertex more than once, but in this case
each cycle formed must be even, implying that the face has an even

number of sides.

Theorem 8.4. If F = 2qr in a 2-cell imbedding of K in a

3 Paqsr
= ip-2)iq+r-Zl l -_
Clyr) S Y(M) 4 + 4 2 (1 2)F21‘

surface M, then v(K
p i23

3

58

Proof: We use the Euler-type formula (I) discussed in Chapter

1
4: v(G) = l +--' 2 (i-4)(Fi+Vi). In particular, for G = K

8 123 p,q,r’
Since Vp+q - r, Vp+r = q, Vq+r = p, and Since we are assuming that
F3 = 2qr, we have, using Lemma 8.3,
K )sM
V< p.q.r Y< )

1 .
1 + §(—2rq + (pm-4)]: + (p+r-4)q + (qfi'4)p)

+

ooh—-

2 (i-4)F.
i25 1
= Q-Zlmfi-zl + l 2 (i_2)F ..

4 4 . 21
123

As a result of Theorem 8.4, it is possible to show that
equality holds in Theorem 8.1, provided we produce a 2-cell
imbedding of K for which F = 2qr and %(F + 2F + 3F10) =

p,q.r 3 6 8
{lp-2>(q+r-2i} _ (p-2)(q+r-2>
4 4

, with all other faces being quadri-

 

lateral, for then v(Kp q r) s {%p-21§q+r-2) . In particular,

if (p-2)£q+r-21

F3 = 2qr and F

is an integer, we seek a 2-cell imbedding with
4 = F - F3. This search utilizes Edmond's permutation
technique, which produces only 2-cell imbeddings.

Before proceeding with this plan, let us state the following
corollary of Theorem 8.4, which is not employed in the remainder
of this chapter, but is of interest in its own right, since it

indicates that a minimal imbedding of Kp q r cannot in general be

triangular.

 

Corollaryi8.5. A minimal imbedding of Kp r is triangular if and

A.

only if p = q = r.

 

Proof: (i) Ringel and Youngs have shown that v(Kp p p) =
LP'I;(E'2), with F = F3.

59

(ii) Suppose Kp q has a triangular imbedding. This

3 3

imbedding is therefore minimal, by a result of Youngs, and hence

is a 2-ce11 imbedding. Then F = F3 = 2qr, since F3

edge of type 1 lies in exactly two triangular faces for this

s 2qr; and each

imbedding, so that F3 2 2qr also. Then, by Theorems 8.1 and 8.4,

= (13-2) (q+r-2)
V(K 4

p q r Now, from the Euler formula,
3 9

2qr = F -v + E + 2(1-v)

-(p+q+r) + (M + pr + qr) + 2 - %(p-2)(q+r-2).

so that pq + pr = 2qr. Since p 2 q 2 r, then pq 2 qr and pr 2 qr.

It follows that pq = qr = pr, and p = q = r.

We have established the preliminary results needed to show

that y(K ) = (P-2)£(q+r-gl

P:Q:r
the nine case—S: (Cur) = (1,1); (2.1); (3,1), (2,2); (4,1), (3,2);

, when 2 s q + r s 6. We treat

(5,1), (4,2), and (3,3) in the theorems that follow. We first
note that if q = r = l, the graph is planar and the genus formula

clearly holds; see Figure 8.1. In this case, F = 2, F - l,

3 4:?

and F = F3 + F4. Euler's formula is satisfied, with v = 0.

 

Figure 8.1 An imbedding of K in the plane.

12.1.1

The remaining cases are more involved and are handled by the use

of Edmonds' permutation technique, discussed in Chapter 3.

60

Theorem 8. 6. The genus of the graph K

{}L-i}, for p 2 2.

Proof: By Theorem 8.1, v(K

is given by V(K

p,2,l p,2,l) =

p 2 1) 2 2&3- . We show that

v(Kp 2 1) —:{‘L‘:—} by exhibiting, for each p =5 2 (mod 4), an

appropriate imbedding. The result will then follow, since if

p0= 2 (mod 4) and m = pO , pO -1, pO -2, or pO -3, then V(Km,2,1)

p0 -2 _
s y(Kp 2 1) ${—-— }= (){T 23.3 0, we claim that Y<Kp,2,1)
s {%i— , for p E 2 (mod 4). By Theorem 8.4, it suffices to
produce a 2-cell imbedding with F3 = 4 and F4 = F - F3. We employ

Edmonds' permutation technique:

{2,3;4,...,p+3} , i = 1

V(i) = {l;4,...,p+3} , i = 2,3
[1;2,3} , i = 4,...,p+3
.rp+2, i = 1
n(i) =< p+l, i = 2,3

 

3, 1 = 4,...,p+3
k

pl: (9+3.p+2.---.6.5;3.4.2)
92: (1.4;p+1.p+2;p-3.p-2;---:7.8:5,6;9.10..--.p-1.p;p+3)
p3: (1,5;8,9,6,7;lZ,l3,lO,ll;...;p+2,p+3,p,p+l;4)

P43P63°°'app+2: (1,3,2)

p53P72°-°,pp+3: (19223)

The permutation P determined by these pi, i = 1,...,p+3,
(see Chapter 3) applies for all p E 2 (mod 4) except for p = 2;

but then 0 s v(K ) s v(K ) = 0, by the result of Ringel

2,2,1 2,2,2

and Youngs, so that this case is trivial. Now, we compute the

61
orbits under P as defined above:
(i) F3 = 4: l-(p+3)-2; l-2-4; 1-3-5; 1-4-3.

We note that at this stage all edges of type I have been accounted
for.

(ii) F4 = F - F 1-(2m-l)-2-2m, m = 3... 2+1

3.
l-2m-3-(2m+l), m = 3,... 2+1

(Now all edges of tyep II have been accounted for.)

2-5-3-8

2-(p+1)-3-4

2-(2m-1)-3-(2m-4), if (2m-1) 1 (mod 4)

2-(2m-1)-3-(2m+4), if (2m-1) 3 (mod 4)

m

(m = 4,...,P—+2, m #gfl)
Now all edges of type III have also been taken into account. We
have shown that every directed edge not in a triangular face is

in a quadrilateral face. This completes the proof.

The above representation allows us to count the number of
faces directly: F = 6 + 2912’- + 1 - 2) + (g + 2 - 4) = g2 + 2, which
is consistent with the Euler formula, as indeed it must be. We
observe also that removing vertices p+i,...,p+3, i = 1,2, or 3,

gives a minimal imbedding for Kp+i-4,2,1'

Theorem 8.7. The genus of the graph K is given by v(K ) =

{?€?{}, fom p 2 3.

Proof: By reasoning similar to that employed in the proof of

P9331 F3391

Theorem 8.6, it suffices to produce a 2-cell imbedding of Kp 3 1,
3 3

for all p E 0 (mod 2), for which F3 = 6 and F4 = F - F3. Such

an imbedding is given by:

62

p1: (p+4,p+3,...,9,8;4,7,3,6,2,5)
p2: (l,6;p+4,p+3,...,8,7;5)
(l;7,8,...,p+3,p+4;5,6)
(l;8,9,...,p+3,p+4;6,5,7)

p5: (l,2,4,3)

p6: (1,3,4,2)

p7,p9,...,pp+3: (1,4,2,3)

p83p103'°'app+4: (1339234)

The orbits determined by P for these pi, i = l,...,p+4, are:
(i) F3 = 6: 1-2-6; 1-3-7; 1-4-8;
1-5-2; 1-6-3; 1-7-4.
(ii) F4 = F - F3: l-(p+4)-3-5
1-(2m-1)-4-2m, m = 5,... 2+2

’2
l-(Zm-2)-3-(2m-l), m = 5,...,§+2
2-(p+4)-4-6
3-6-4-5
4-7-2-5
2-(2m-1)-3-2m, m = 4 ...,§+2
2-(2m-2)-4-(2m-l), m = 5,...,§+2

Here we have F = F3 +-F4 = 10 + 305 + 2 - 4) + (E + 2 - 3) = 2p + 3,

which checks with the Euler formula. Removing vertex (p+4) in the

above representation gives a minimal imbedding of Kp 1 3 1.
"'9,

Theorem 8.8. The genus of the graph K

{%%%} , for p 2 2.

Proof: We have only to add two suitably chosen edges in the

 

is given by v(Kp

p.2.2 .2.2) =

63

imbedding of Theorem 8.7, and delete an appropriate edge, to obtain

a minimal imbedding for K for all p # 2. Recall that v(K

p,2,2’ 2,2,2)

= 0, by the result of Ringel and Youngs. For p # 2, delete edge
(1,2); and add edge (2,3) in face 2-7-3-8, and edge (2,4) in face

2-(p+4)-4-6. The permutation representation becomes:

p1: (p+43p+33’"39383437333635)

p2: (6,4;p+4,p+3,...,9,8;3,7,5)

p3: (1,7,2;8,9,...,p+3,p+4;5,6)

p4: (1;8,9,...,p+3,p+4;2,6,5,7)

p5: (l,2,4,3)

p6: (1,3,4,2)

p7,p9,...,pp+3: (l,4,2,3)
(l,3,2,4)

p83p103° " '3Ppfiz

For p odd, delete vertex p+4 from the above imbedding.

The general method of proof for the remaining cases q+r s 6
follows that employed above. We give the pertinent permutations

for each case, but omit the straightforward counting of orbits.

Theorem 8.9. The genus of the graph 1(1),,”1 is given by v(Kp’4,1) =

{%$£;Z%} , for p 2 4.

Proof: (1) For p E 2 (mod 4), the following imbedding has

F3 = 8 and F4 = F - F3:

64

p1: (p+5,p+4,...,ll,10;5,9,4,8,3,7,2,6)

p2: (1,7;p+5,p+2,p+3,p+4;p+l,p-2,p-l,p;...;15,12,l3,l4;8,ll,
10,9,6)

(1,8;11,12,...,p+4,p+5;6,9,10,7)

(l,9,6;p+2,p+5,p+4,p+3;p-2,p+l,p,p-1;...;12,15,l4,13;7,
10,11,8)

p5: (l,lO,11,8;l4,15;l8,l9;...;p+4,p+5;7;13,12;l7,l6;...;
p+3,p+2;6,9)

p6: (1,2,5,4,3)

p7: (1,3,4,5,2)

(l,4,2,5,3)

p9: (1.5.2.3.4)

p10: (1,4,3,2,5)
p11: (l,3,5,2,4)
p12,p16,...,pp+2: (l,2,4,5,3)
p13,p17,...,pp+3: (l,3,5,4,2)
p14,p18,...,pp+4: (1,5,2,4,3)
p15,p19,...,pp+5: (l,3,4,2,5)

(ii) For p E 1 (mod 4), remove vertex p+5 from the imbedding in
case (i). The genus is unaffected. Here, F6 +2F8 +3F10 = 3.

(iii) For p s 0 (mod 4), remove vertices p+4 and p+5 from the
permutation representation of case (f). This lowers the genus by

one, which may most readily be seen from the Euler formula, noting

that AV 3 -2, AB = -10, and AF = -6. We have F + 2F = 2, unless

6 8
= ' = = 4 d = = l.
p 4, in which case F3 7, F4 , an F5 F6
(iv) For p 5 3 (mod 4), the following imbedding has F = 8,

3

65

p1: (p+5,p+4,...,11,10;5,9,4,8,3,7,2,6)
.pz: (1,7;p+5,p+2,p+3,p+4;p+1,p-2,p-l,p;...;l6,13,l4,15;9,8,
12,10,ll,6)
(1,8,9,ll,10;13,14,...,p+4,p+5;6,12,7)
(1,9;15,l6;l9,20;...;p+4,p+5;7,10,ll,12,6;14,l3;18,17;
.;p+3,p+2;8)

95: (1.10.7.12.8;p+2.p+5.p+4.p+3;p-2,p+1.p.p-1;---;13.16.15,14;

 

6,11,9)
p6: (132353433)
p7: (133353432)
p8: (134353233)
p9: (135333234)
p10: (1.2.3.4.5>
p1,: (1.4.3.5.2)
p12: (132353334)
p13’p173'°'3Pp+2: (132353493)
p143p189"'3pp+3: (133349522)
pl,»p1,.---.pp,,: (l,4,2,5,3)
P163P20,--.,pp+5: (l,3,5,2,4)
Theorem 8.10. The genus of the graph Kp,3,2 is given by V(KP33,2) =

{é‘flgg} , for p 2 3.

Proof: For p = 3, we have 'Y(K3,3,2

is clearly a subgraph. But v(K

) 2 l by Kuratowski's
theorem, since K3,3 3,3,2) 3 v(K3,3’3)
= l, by the result of Ringel and Youngs. Thus the theorem holds for
p = 3. For p 2 4, we add the three edges (2,3), (2,4), and (2,5),

and delete the edge (1,2), in the imbedding given in Theorem 8.9.

For p £ 3 (mod 4), we then have:

p6,...

66

(p+5,p+4,...,ll,10;5,9,4,8,3,7,6)
(7;p+5,p+2,p+3,p+4;p+l,p-2,p-l,p;...;15,12,13,l4;8,4,ll,
10,3,9,5,6)
(1,8;11,12,...,p+4,p+5;6,9,2,10,7)
(1,9,6;p+2,p+5,p+4,p+3;p-2,p+1,p,p-l;...;12,15,14,13;7,
10,11,2,8)
(l,lO,ll,8;14,15;18,19;...;p+4,p+5;7;13,12;17,16;...;
p+3,p+2;6,2,9)

,p as in Theorem 8.9 for p a 2 (mod 4).

p+5=

Recall that for the cases p a 1 (mod 4) and p a 0 (mod 4), we

must remove vertices p+5 and then p+4 respectively. For p a 3 (mod 4),

we have:

p6,...

Theorem 8.11. The genus of the graph Kp

(p+5,p+4,...,11,10;5,9,4,8,3,7,6)
(7;p+5,p+2,p+3,p+4;p+l,p-2,p-l,p;...;16,13,14,15;4,9,3,
8,12,10,1l,5,6)
(1,8,2,9,11,lO;13,14,...,p+4,p+5;6,12,7)
(1,9,2;15,16;19,20;...;p+4,p+5;7,lO,11,12,6;14,l3;18,17;
.;p+3,p+2;8)
(1,lO,7,12,8;p+2,p+5,p+4,p+3;p-2,p+l,p,p-l;...;13,16,15,14;
6,2,11,9)

,pp+5: as in Theorem 8.9 for p 5 3 (mod 4).

35,1 is given by Y<KP3531) =

p-2, for p 2 5.

Proof: We distinguish two cases, p odd and p even. In either

case, the imbedding presented has F3 = 10, F

4 = F - 10 = 3p - 5.

67

Case (i); p odd:

p1: (p+6,p+5,...,12,ll;6,10,5,9,4,8,3,7,2)
p2: (l,7,10,9,8;ll,12,...,p+5,p+6)

p3: (1,8,9,11,10;13,12;15,14;...;p+6,p+5;7)
(l,9,lO,ll;p+6,p+5,...,13,12;7,8)

p5: (1,10,7;12,13,...,p+5,p+6;ll,8,9)

p6: (l,ll,9,8,7;p+5,p+6;p+3,p+4;...;12,l3;10)
p7: (2,1,3,6,4,5)

(3,1,4,6,5,2)

p9: (4,1,5,6,3,2)

p10: (5,1,6,3,4,2)

p11: (63132353433)

912.914,---.pp+5: (1.6.3.5.4,2)

p13.915.---.pp+6= (1.2.4.5.3.6)

Case (ii); p even:

p1: (p+6,p+5,...,12,11;6,10,5,9,4,8,3,7,2)

p2: (1,7,9,11,10,8;12,13,...,p+5,p+6)
(1,8,10,12,11,9;13,l4,...,p+5,p+6;7)
(l,9,7;14,13;16,15;...;p+6,p+5;11,12,lO,8)
p5: (1,10,11;p+5,p+6;p+3,p+4;...;13,14;7,12,8,9)
p6: (1,11,12,7;p+6,p+5,...,l4,13;9,8,10)

p7: (2.1.3.6.5.4)

p8: (3,1,4,6,5,2)
p9: (43135363332)
<5.1.6.4.3.2>

68

p11: (63134353233)
p1,: (1.2.5.6.3.4>
p13’p153°°'3pp+5: (13336353432)

914.p16..--.pp+6= (1.2.4.5.6.3)

Theorem 8.12. The genus of the graph K is given by y(K

p,4,2) =

 

p,4,2
p-2, for p 2 4. ..
‘nggf: Here we distinguish three cases. The imbeddings in the
first two of these cases are derived from those of Theorem 8.11,
deleting edge (1,4) and adding edges (4,2), (4,3), (4,5), and (4,6)

within appropriate faces.

Case (i); p odd:

p1: (p+6,p+5,...,12,11;6,10,5,9,8,3,7,2)

p2: (1,7,10,4,9,8;11,12,...,p+5,p+6)
(1,8,9,11,4,10;13,12;15,14;...;p+6,p+5;7)
(9,2,10,3,11;p+6,p+5,...,l3,12;5,7,6,8)

p5: (l,lO,7,4;12,13,...,p+5,p+6;ll,8,9)

p6: (l,ll,9,8,4,7;p+5,p+6;p+3,p+4;...;12,13;10)

p7,...,pp+6: as in Theorem 8.11, for p odd.

Case (ii); p even; p 2 6:

p1: (p+6,p+5,...,12,11;6,10,5,9,8,3,7,2)

p2: (1,7,4,9,11,10,8;12,13,...,p+5,p+6)
(1,8,10,4,12,11,9;13,14,...,p+5,p+6;7)
(9,2,7,5;14,13;l6,15;...;p+6,p+5;ll,12,3,10,6,8)

p5: (1,10,11;p+5,p+6;p+3,p+4;...;13,l4;4,7,12,8,9)

69
p6: (1,11,12,7;p+6,p+5,...,14,13;9,8,4,10)

p7,...,pp+6: as in Theorem 8.11, for p even.

Case (iii); p = 4:

p1: (10.6.9.5.8,4.7.3) p6: (9.1.10.8.2,7>
p2: (3.9.4.10.5.7,6.8> p7: (3.1.4.6.2.5)
p3: (103137393238) p8: (43135333236)
p4: (7.1.8.10.2.9> p9: (5.1.6.4,2.3)
p5: (8,1,9,7,2,10) p10: (6,1,3,5,2,4)

Theorem 8.13. The genus of the graph Kp,3,3 is given by v(Kp,3,3) =
p-2, for p 2 3.

Egggf; Here we treat four cases. The imbeddings in the first
two of these cases are derived from those of Theorem 8.11, deleting
edges (1,3) and (1,5), and adding edges (i,2), (i,4), and (i,6),
for i = 3,5.

Case (i); p odd, p 2 5:

p1: (p+6,p+5,...,12,ll;6,10,9,4,8,7,2)

p2: (1,7,5,10,9,3,8;ll,12,...,p+5,p+6)
(8,2,9,6,11,4,10;13,12;15,14;...;p+6,p+5;7)
(1,9,10,3,11;p+6,p+5,...,l3,12;5,7,8)

p5: (10,2,7,4;12,13,...,p+5,p+6;ll,8,6,9)

p6: (1,11,3,9,5,8,7;p+5,p+6;p+3,p+4;...;12,13;10)

... : .11, dd.
p7, ’pp+6 as in Theorem 8 for p o

70

Case (ii); p even, p 2 6:

p1: (p+6,p+5,...,12,ll;6,10,9,4,8,7,2)

p2: (1,7,9,11,5,10,3,8;12,13,...,p+5,p+6)

p3: (8,2,10,4,12,6,11,9313,14,...,p+5,p+6;7)
(1,9,7,5;l4,13;16,15;...;p+6,p+5;11,12,3,10,8)
p5: (10,2,11;p+5,p+6;p+3,p+4;...;13,14;4,7,6,12,8,9)
p6: (l,ll,3,12,5,7;p+6,p+5,...,14,13;9,8,10)

p7,...,pp+6: as in Theorem 8.11, for p even.

Case (iii); p = 3: v(K3 3 3) = l, by the result of Ringel and
3 3
Youngs.

Case (iv); p = 4:

p1: (10,6,9,5,8,4,7) p6: (9,1,10,2,7,3,8)
p2: (7,6,10,4,9,8,5) p7: (1,4,3,6,2,5)
p3: (5,9,8,6,7,4,10) p8: (4,1,5,2,6,3)
p4: (7,1,8,9,2,10,3) p9: (5,1,6,2,4,3)
p5: (8,1,9,3,10,7,2) p10: (6,1,5,3,4,2)

We now combine Theorems 8.6 through 8.13 into one theorem:

Theorem 8.14. The genus of the graph Kp q r is given by v(K ) =

3 3 p3q3r
{39-22(Q+T'2{} , where p 2 q-2 r and q+r s 6.

 

 

We have conjectured that the above result holds for all values
of q+r. It is likely that the case q+r = 7 could be handled as
above, and then q+r = 8, and so on; but some more general approach

would seem to be desirable.

71

As a result of Theorem 8.14, we can make the following

observation:

Theorem 8.15. In any minimal imbedding of Kp r’ for q+r s 6,

:Q:

every handle carries at least one edge of type II or of type 111.

Proof: Assume to the contrary that there is a handle of this

ip-Z)éq+T-22

Removing all type I edges in the imbedding, we obtain an imbedding

surface of genus which carries only edges of type I.

t

of the graph KP q+f on the same surface. But the handle that
3

formerly carried only edges of type I now contains no part of the

p q+r’ and hence the face of the new imbedding containing
3

this handle is not a 2-cell. This imbedding of K

graph K

p q+r’ then, is
3

not minimal, so that v(Kp q+r) < {?P-2)éq+r'2{} , contradicting

 

Ringel's formula for the genus of complete bipartite graphs.

We conclude this chapter with one further result concerning

the genus of complete tripartite graphs:

Theorem 8.16. The genus of the graph Km

n,n,n is given by V(Kmn )
= (mm-2) (n- 1)
2

anan

, for all natural numbers m and n.

Proof: It suffices to produce an imbedding of K for
--- mn,n,n

which F3 = 2n2 and F4 = F - F3. We start with the following

imbedding of Kmn 2n (which differs from Ringel's imbedding for the
3

2 -2 -1
same graph, unless n = 2), having F = F4 = mn and y = (mn )(n 2:

{2n+l,...,2n+mn} , i = 1,...,2n

V(i) =
{1,...,2n} , i = 2n+l,...,2n+mn

72

p1,p3,...,p2n_1: (2n+l,2n+2,...,2n+mn)
p2,p4,...,p2n: (2n+mn,2n+mn-l,...,2n+l)

p2n+i: (1,21,3,21-2,5,2i-4,7,...,2n-l,2i+2), i = 1,...,mn;

where arithmetic is modulo 2n, and we write 2n instead of 0.
The orbits(faces) are:

(2j-1)-(2n+i)-(21-2j+2)-(2n+i-l), for j = 1,...,n; i = 2,...,mn
(2j-l)-(2n+i)-(2i-2j+2)-(2n+mn), for j = 1,...,n; i = 1, where
the third entry only, in each of the above representations of orbits,
is reduced modulo 2n, with 2n being written instead of 0.
We now add edges (2j-1,2k), j = 1,...,n and k = 1,...,n,
through the faces determined by i = k + j - 1 respectively. These

2
are precisely the n edges of type I needed to convert the graph

mn,2n to the graph Kmn,n,n' Each such edge destroys one quadri-
lateral face and creates two triangular faces, so that K
mn,n,n
2
is imbedded with F = 2n2 and F = F - F = mn - n2. This is

3 4 3
the desired imbedding.

B IB LIOGRAPHY

10.

ll.

12.

13.

14.

15.

BIBLIOGRAPHY

L. Auslander, T. A. Brown, and J. W. T. Youngs. The Imbedding
of Graphs in Manifolds. J. Math. Mech. 12 (1963), 629-634.

J. Battle, F. Harary, Y. Kodama, and J. W. T. Youngs. Additivity
of the Genus of a Graph. Bull. Amer. Math. Soc. p8 (1962),
565-568.

M. Behzad and G. Chartrand. An Introduction to the Theorygof
Graphs. (to appear)

L. W. Beineke and F. Harary. The Genus of the n-cube. Can. J.
Math. 11 (1965), 494-496.

J. Dugundji. Topology. Allyn and Bacon, Boston (1965).

R. Duke. Minimal Imbeddings and Open Mappings of Graphs in
Manifolds. Ph.D. Thesis, Univ. of Virginia (1965).

J. Edmonds. A Combinatorial Representation for Polyhedral
Surfaces. Notices Amer. Math. Soc. 1 (1960), 646.

W. Gustin. Orientable Embedding of Cayley Graphs. Bull. Amer.
Math. Soc. 92 (1963), 272-275.

F. Harary. Graph Theory. Addison-Wesley, Reading (1969).

 

F. Harary. Some Historical and Intuitive Aspects of Graph
Theopy. SIAM Review 2 (1960), 123-131.

P. J. Heawood. Map Colour Theorem. Quart. J. Math. Oxford
Ser. gfl_(1890), 332-338.

G. Kuratowski. Sur le Probléme des Courbes Gauches en Topologie.
Fund. Math. l§_(1930), 271-283.

W. S. Massey. Algebraic Topology; an Introduction. Harcourt,
Brace, and World (1967).

J. Mayer. Le Probléme des Régions Voisines sur les Surfaces
Closes Orientables. J. Comb. Th. p (1969), 177-195.

E. M. Palmer. Prime Line Graphs. Elem. Math. (to appear)

73

16.

17.

18.

19.

20.

21.

22.

23.

24.

25.

26.

27.

28.

29.

74

G. Ringel. Uber Drei Kombinatorische Probleme am n-dimensionalen
Wfirfel und Wfirfelgitter. Abh. Math. Sem. Univ. Hamburg 29 (1955),
10-19.

G. Ringel. Farbungsprobleme auf Flachen und Graphen. Deutscher
Verlag, Berlin (1959).

G. Ringel. Das Geschlecht des Vollstandigen Paaren Graphen.
Abh. Math. Sem. Univ. Hamburg 28 (1965), 139-150.

G. Ringel. Der Vollstandige Paare Graph auf Nichtorientier-
baren Flachen. J. Reine Angew. Math. 220 (1965), 88-93.

C. Ringel and J. W. T. Youngs. Das Geschlecht des Symmetrische
Vollstandige Drei-Farbaren Graphen. Comment. Math. Helv.
(to appear)

G. Ringel and J. W. T. Youngs. Solution of the Heawood Map-
Coloring Problem. Nat. Acad. Sci. p9 (1968), 438-445.

 

E. H. Spanier. Algebraic T0pology. McGraw-Hill (1966).

C. M. Terry, L. R.‘Welch, and J. W. T. Youngs. The Genus of
K12 . J. Comb. Th. _2_ (1967), 43-60.

___E
W. Vollmerhaus. "Uber die Einbettung von Graphen in Zwei-
dimensionale Orientierbare Mannigfaltigkeiten Kleinsten
Geschlechts," in Beitrage Zur Graphentheorie. Teubner, Leipzig
(1968),.163-167.

J. W. T. Youngs. "The Heawood Map Coloring Conjecture," in
Graph Theory and Theoretical Physics. Academic Press, London
(1967), 313-354.

 

J. W. T. Youngs. Irreducible Graphs. Bull. Amer. Math. Soc.
Z__(l964),.404-405.

J. W. T. Youngs. Minimal Imbeddings and the Genus of a Graph.
J. Math. Mech. 12 (1963), 303-315.

J' W. T- Youngs. The Nonorientable Genus of K . Bull. Amer.
Math. Soc. 14 (1968), 354-358. .2

J. W. T. Youngs. Remarks on the Heawood Conjecture (Non-
orientable Case.) Bull. Amer. Math. Soc. 14 (1968), 347-353.

 

   

MICHIGAN STATE UNIVERSITY LI'BRARIES
'I
IIIIIIIHIHIIIIIIIIIWIIIIIIINIIIIIIWIIIIIIIHIIIH
3 1293 03143 2358