THE MAXIMUM GENUS OF A GRAPH

MICHIGAN STATE UNIVERSITY
RICHARD DELOSE RINGEISEN

I

I

’ Thesis for the Degree of Ph. D.
19 70

 

 

 
  

LIBRARY

 

 

 

THF‘EIS . \
Michigan State
“cu—~— w
This is to certify that the
thesis entitled
The Maximal Genus of 3 Graph I
presented by
Richard Doloso Ringoison
has been accepted towards fulfillment
of the requirements for
Ph. D. degree in Mathematic-
fiflW/r—
Major professor
Date % /0,1 /7 10
V J
0-169

       

mm ‘1
’5 am‘oma av ‘5 I
: HUAG & SUNS'
wgzeyme I

ABSTRACT
THE MAXIMUM GENUS OF A GRAPH
By
Richard Delose Ringeisen

In 1965, R. Duke considered inbeddings of graphs which were not
necessarily nininal, but which were cellular (2-cell) inbeddings.

Such considerations led to the concept of the maxi-us genus of a con-
nected graph.

The narinun genus,‘yn(c), of a connected graph G is the largest
integer Y(N) for conpact orientable Z-nanifolds N in which a has a
cellular inbedding, where Y(N) is the genus of the surface N. In
1969, Nordhaus, Stewart, and Hhite made the above definition and stud-
ied sons of the properties of sari-us genus. It is the purpose of
this thesis to extend the knowledge of this concept. Sole new maxi-us
genus fornulas are obtained and an investigation is nade of graphs which
do or do not attain certain bounds for the naxinun genus.

Two techniques to obtain inbeddings of graphs are frequently used
in the thesis, one of which is Ednonds' pernutation technique, and the
other an edge adding or ribbon technique which provides a cellular
inbedding for a graph.fron a cellular inbedding of a suitably chosen
subgraph.

The first three chapters of the thesis introduce the subject,
define basic terns and techniques, and survey known results pertinent

to the study of genus problens.

Richard Delose Ringeisen

In Chapter’h, the naxinun genus of certain planar graphs is deterb
lined. This class includes the wheel graphs, the ladder graphs, the
standard waxinal planar graphs, and the regular polyhedral graphs.

In Chapter 5 sone general properties of sari-us genus are presented.
A najor problen concerns the determination of those connected graphs
for which the sari-um genus is the sun of the sari-us genera of its
conponents. Sone results pointing toward a possible couplets solution
to this problem are given. In particular, if 61 and 62 are two con-
nected disjoint graphs which are joined hy a single edge to fora.a
new graph G, we show that yn(c) - Yw(°1) + “(02). A conplete char-
acterization of those graphs for which the narinun genus and the sini-
nun genus are equal is presented. Those graphs with narinun genus one
are also deter-ined.

Chapter 6 treats those graphs which we designate as either upper
or lower inbeddable. A conjecture nade by Duke is proven true for
lower inbeddable graphs, and for certain other classes of graphs.

In Chapter 7, the naxinun genus of the conplete bipartite graph
Kn,n is deternined,.and the formula, YH(Kn,n) - [%(n-l)(n-ll], is
proven. The narinun genus of the complete graph, although known pre-
viously, is deter-ined in a different way using an edge adding tech-

nique.

THE MAXIMUM GENUS OF A GRAPH

By
Richard Delose Ringeieen

A.THISI8
Suhnitted to
Michigan State University

in partial fulfillnent of the requirements
for the degree of

DOCTOR OF PHILOSOPHY

Departnent of Mathematics
1970

é~ Q5559

/- .942» ‘7/

For Carolyn.
Mon and Dad

ii

ACKNOWWTS

I wish to thank Professor E. A. Nordlnus. without whose guidance
and inspiration this thesis would never have been possible. Hare than
that. however. I an grateful for the appreciation for Graph Theory which
he has given as.

W gratitude also is extended to Professor B. M. Stewart for the
tins and energy he has given to this thesis.

I would also like to thank Professors J. G. Hocking. E. H. Pal-er.
G. D. Taylor. an! A. '1‘. White for the help and guidame given as through-
out w doctoral program.

This research was supported in part by National Science Fbundation
Grant GU 26168.

111

TABLE OF CONTENTS

Chapter

l.Introduction.....................
2. Definitions. Notations. and Techniques . . . . . . . .
3.ASurveyofKnownBesults..............
1+. The Minn Genus of Certain Planar Graphs . . . . . .
5. Properties of the Maximum Genus of a Graph . . . . . .
6. Upper and Lower Inbeddable Graphs . . . . . . . . . .

7. The Mariana Genus of the Conplete Bipartite Graph K. n
andtheConpleteGrathn eeoeeeeeeeoee'e

Bibli ompm O O O O O O O O O O O O O O O O 0 C O O O O 0

iv

Page

13
19

58

71+

LIST OF FIGURE

Figure

2.1
2.2
2.3
2.4
3.1
3.2
4.1
11.2
u.3
5.1
5.2
5-3
5.4-
6.1

A Cellular Inbedding of Kit on the Torus .
ThePetersenGraph ...........
Illustration of the Edge Adding Technique
K3 with a Vortex and Two Edges Added . .
Two Graphs which are not Upper Iabeddable
TheGrath...............
TheRegularPolyhedralGraphs......
The Dcdecahedral Graph with Pernutations
Adding Elges for the Icosahedral Graph .
TheGraphsI-Iandq ...........
ObtainingtheGrath..........
ThreeNewKindschraphs........
Obtaining a Block of . Nauru Genus One .

moraph an O O O O“. O O O O O O O O O

ssssueeg’

33
33

45
48

5?
68

CHAPTH 1
IMROWC‘I‘ION

It was only in recent years that graph theorists began to concern
themselves with the topological properties of a graph. The early con-
siderations of such concepts were a direct result of the faaous four
color conjecture and its graph theoretical interpretation. However.
natheaaticians soon began to consider the genus of a graph primarily
for the properties of the graph which it night yield.

In 1965. Richard Duke [4] considered imbeddings of graphs which
were not necessarily minim but which have each of their faces homeo-
aorphic to an open disk. In particular. he raised the following ques-
tion: Upon which conpact orientable two manifolds might a given graph
have such a cellular iabedding? Such considerations led to the concept
of the nan-um genus of a connected graph. Is there a surface of laxi-
aum genus upon which a given graph G has a cellular iabedding? It was
soon discovered that the well known Euler Polyhedral formula provides
an upper bound. In 1969. Nordhaus. Stewart. and White [10] defined
the maxim genus of a graph and studied cone of its properties.

It is the purpose of this thesis to extend the knowledge of this
concept. Soae maxim genus for-alas are obtained and an investigation
is made of graphs which do or do not attain maneu- genus.

The definitions. notations. and techniques used in this thesis
are stated in Chapter 2. Of particular interest is the deve10paent of

l

2
an edge adding technique. which is widely employed throughout the
thesis. Chapter 3 makes a survey of results of importance known prior
to this thesis. Both pertinent results concerning ordinary genus and
those relative to nanuuu genus are discussed.

In Chapter 4 the maxim genera of sous well known planar graphs
are found. Formulas for the standard maxiual planar graph. the wheel
graph. the ladder graph. and the polyhedral graphs are given.

In Chapter 5. sons of the uain results of this thesis are presented.
An important question concerns the determination of those connected
graphs for which the maxim genus is the sun of the uaxiuuu genera
of the couponsnts. Sous results pointing toward a possible couplets
solution to this problen are given. A complete characterisation of
these graphs for which uuiuuu genus and ordinary genus are equal is
presented. These graphs which have unnuuu genus one are also charac-
terised. Chapter 6 concerns itself with these graphs which we desig-
nate as either upper or lower imbeddable. Sous additional genera for-
uulas are given.

Chapter 7 contains two results of special interest. The uaxiuuu
genus formula for the couplets bipartite graph is derived. The uaxiuuu
genus of the couplets graph is also given. although this result was
established by different procedures prior to this thesis [10] .

CHAPTER 2
DWINITIOI‘B, NOIATIONS, AND TERRIQUB

This chapter: defines those tens which are fundamental to the study
of topological properties in mph theory‘. is also present those tech-
niques which are often employed in the later chapters of this thesis.

A m c. is a set of vmiees v(c) and a set of unordered pairs
of vertices 3(a), called m. If the elenents of 3(a) are ordered
pairs, G is a directed m. For two wartices x and y in V(G), (x.y)
represents the corresponding edge (if any) in s(c). If G is a directed
graph, the corresponding edge directed from x to y is denoted [my] .
(This notation is that which is used by Youngs [15] .) An edge of the
fora (1,1) is called a 1.922. When an edge appears more than once in
3(a), c is called a m. A graph in which both v(c) and 3(6)
are finite is called 39m. A graph is connected if every pair of
vertices is joined by a path of edges and vertices. A cutpgint of a
graph is a vertex whose removal disconnects the graph. A connected
graph is We if it is connected and has no cutpoints. A £223
of a connected graph is a neural nonseparable subgraph. Henceforth,
we shall only consider graphs which are finite, undirected. connected,
and without loops or multiple edges.

“Owwm («mm on mph c is. bydefl-
nition,B(c)-s-v+1,wheremis thenunbsrof edges ofGandVis
the nnnber of vertices. This nunber is also known as the cyclogtic

3

u
M of G. A graph H is a M of the graph G if v(h)_<_v(c) end
E(H)§E(G). The m of a vertex is the nunber of edges to which it
belongs.

The least integer greater than or equal to a real number s is
written {an}; The greatest integer smaller than or equal to s is written
[5].

Other terns which are not given here say be found in Harary [6].
Topological terns say be found in eithar Dugundji [3] or Massey [8] .

A graph can be thought of in a strictly setdtheeretic sense as a
collection of vartices and edges; However. one can also regard graphs
in a geonetric sense. It is when one attupts such a geonetric reali-
sation that imbedding problem are encountered. Although any graph
can be realised in Euclidean 3-space, the realization need not be in a
Z-aanifoldt By placing this 2’-nanifold restriction on our iabeddings
we encounter some very interesting problels.

The graph G is said to be M in the 2-manifold M if the geo-
setric realisation of G as a oneé-dinensional simplicial complex is
homeonorphic to a subspace of 14. He can state this condition in a nore
graph theoretic fora. Let c be a graph where v(o) - {v1,...,vn75end
3(a) - {’1"“'°nz>‘ An W 2; g is g is a subspace GO!) of n
such that

can - 1(a) uuejm.

where
(i) v1(h),..;.vn(n) are distinct points of M.
(ii) e1(H),..$,en(H) are m nutually disjoint open arcs in H.

5
(iii) ej(H)flv1(h) -¢, 1 - 1,...,n: j - 1.....n.
(iv) if °j - (vjlnjz) then the Open arc eJ(H) has v31“) and
“2(3) as end points; I: - l,...,m.
An & in H is a honeosorphic image of the closed unit interval: an
m gs; is an are less its two end points. the iaages of O and l.
The surfaces considered in this thesis will be conpact orientable 2-
aanifolds. we will use the tars "pm” to reder to compact orienta-
ble 2-manifolds.

Given an iabedding of a graph G on a surface N, each coaponent in
the coapluent of G in N is called a £993 of the iabedding. Ihenevar
a face is hoseoaorphic to the open unit disk. it is said to be a. _2_-g_e_l_l.

If an inbedding is so that each of its faces is a Z-cell, the imbedding is
called a cglular isbeddigg. The total nuaber of faces in an imbedding is
denoted by P. In a cellular imbedding, ’1 denotes the nunber of faces hav-
ing 1 sides, and Vi the number of‘vertices of degree 1.

When a graph can be iabedded in a surface of genus u but cannot be
iabedded in any surface of lower genus, the imbedding is called Egg,
and the gm 2; 21.2 m is defined to be n; we use the notation y(G) - n.
A graph is m if and only if v(c) - o. The nunber of faces in a min-
inal inbedding is denoted 5(a).

Define the sandy}; w, YH(G), 9; a comflg m Q to be the
largest nuaber Yo!) for cospact orientable z-manifolds N in which G has
a cellular imbedding. Such an inbedding is called a gag W.

The nuaber of faces in a narisua iabedding for a graph G is denoted on“)-
Note that if G is not connected. then no isbedding is cellular. The
restriction of consideration to cellular imbeddings is essential, since

otherwise there is no upper bound to the genera of possible surfaces

6
uponwhichagraphaaybeimbedded. Theupparboundwhichcanbede-
tsrmined is given in Chapter 3.

He now turn our attention to the consideration of certain techniques
esployed throughout the thesis. me first is comaonly called ldaonds'
W 12121.99.-

Suppose a connected graph G has n vertices; we write
v(o) -él,...,n}. Let «1) -£hs (1.1:) eE(G)}. Let p1. V(i)-—>V(i)
be a cyclic permutation of v(i) of length n1 - |v(i)| , where i - l,...,n.
The following theorea of ndnonds [5] (also see Youngs [15] ) indicates
the correspondence between cellular imbeddings and choices of the pi.

Theorem hch choice (p1,...,pn) deter-nines a cellular inbedding C(14)
of G in a compact orientable z-sanifold H, such that there is an orien-
tation on h which induces a cyclic ordering of the edges (i,k) at i

in which the immediate successor to (1.1:) is (i,p1(k)), i - l,...,n.

In fact, given (p1,...,pn), there is an algorithm which produces the
determined inbedding. Conversely, given a cellular imbedding GO!) in
a coapact orientable Z-sanifold H with a given orientation, there is

a corresponding (p1,...,pn) deteniniug that iabedding.

Now, let D -2[a,ti : (a,b)€ I(G)3, and define IND—9D by:
P( [n.h]) - [b,pb(a)] . Then P is a per-utetion on the set D of directed
edges of c (where each edge of c. is associated with two oppositely-
directed directed edges), end the orbits under P detersine the faces
of the corresponding inbedding.

Fro: the Edsonds' technique one can conclude that the genus of any
graph and the sari-uh genus of am connected graph can be conputed. It
is a latter of choosing the correct permutation ache-es from thsfi—(ni-l):

cv-

7
possible ones. Of course, the difficulty is in the choosing, because
of the usual enorsous husba- of parsutations possible.
To illustrate this concept, we present an imbedding of the mph
KN the complete graph having It vertioes, on the torus. The imbedding

is that shown in Figure 2.1. The para-stars for this graph are:

mp) - {1.2.3.4}

Ham} for i - 1
{1,3,1}; for i - 2
{1,2A} for i - 3
[1.2.33 for i - t
n(i) - 3, i - 1,2,33.

v(i) J

 

T'ne vertex persutations are seen to be:

p13 (2 lv 3)
pa! (3 1 1*)

 

 

 

 

 

Figure 2.1 A Cellular Isbedding of K” on the Tom

8
This imbedding is cellular, as guaranteed by Edsonds' theores.
He will move later that it is a sauna imbedding. Hence we have
Yuan) - l. we notice that the orbits under P detorsino the faces of
the isbedding, as required. We observe that face (2) has each verter
of Kit repeated, and comsquently, its boundary cannot be a simple

closed curve. The faces are as follows:

m [2.1]:[MJ'[%]:[3'2]
<2> [1.21M 4m].[m1.[a.~1.[~.21.[2d43.1].

These faces correspond to orbits of P and each edge appears as two direc-
ted edges in D, so that the sun of the orbit lengths is 2!.

Henceferth we will use a shorter fora to designate an orbit. For
ere-pl. orbit (1) above will be represented by 4-14-34 This note-‘-
tion isplies that p30?) - z and p2(3) - 1.

As a further illustration of Idsonds' scheae, we detersine the
maxim genus of the Peterson graph P.

m it? The maxim genus of the Peterson graph is three.

my By a theor- which will be given in Chapter 3, we see that
3 is an upper bound for possible genera. Hence, if we can produce an
imbedding of P on a surface of guns 3, the resark is established. We
label the ten vsrtices of P as in Figure 2.2.

    

5,

 

Figure 2.2 The Petersen Graph

9
Choose the following permutations for the wertices of Pa

pl: (5 2 9) P6' (7 10 5)
p2! (1 7 3) p78 (2 8 6)
p3. (10 u 2) p88 (it 7 9)
put (5 8 3) p9! (8 1 10)
p5! (1 1* 6) p108(6 3 9).

He then have a cellular imbedding of P with the following single
orbit of length 30:

-1-2-7-8-9-1-54-8-7-6-10-3J+-5-6-7-2-3-10-9-8-#-3-2-1-9-10-6-5- .

Since this lust he a cellular iabedding, Ma's polyhedral forsula
applies to yield the fact that the genus of the surface upon which the
graph is iabedded is 3. The ressrk is thus established. Notice that
Edaonds' technique does not necessarily yield a unique iabedding of genus
3. However, in probleas of this kind, to produce one iabedding suffices.

The E82 Ltdgipg Technigug offers an alternative to the technique
of ldaonds. It could be characterized as a constructive procedure.
The value of the aethod lies in its allowing one to construct an iabed-
ding for a graph froa an iabedding for a suitable subgraph. He will
state a theor. which describes the technique, indicates its proof, and
illustrates its use.

W: (The use Adding Technique). Let c be a connected graph
which is not couplets and i and J denote nonsdjacent vertices of G.

Let T‘ be a cellular iabedding of G which has vertex i appearing in a

10

i
with the edge (1,5) added. when:

face! andvertexj appearing inaface 13. Let G' bethe grath

a.) If 11 ,1 r3, 6' has a cellular inbedding with one less face
then '1'.
b.) If r1 - 13, then G' has a cellular iabedding with one acre
face than 1'. Furthermore, the directed edges [1,3] and [5,1]
appear in different faces of this iabedding for G'.
2:32;: [10] Let p1 end p 3 be the vertex perlutations at 1 end j
which correspond to the iabedding T‘. Then p1 and p1 nay be represented

as follows: ( issue 1‘ has F1. "an-141.... end F3, ...y'-J-y1... .)
p1! (xlexzmugl): p3! (hare-nil).

Porn an iabedding for G' by leaving all vertex permutations for '1‘ un-
changed, with the exception of those at p1 and p 5' In place of these
two persutations we define:

pit (fioxzuo-exnod): p38 (Ilay2.---.y..1).

Under this new pmutation ache-e for G' the two faces of a.) becoae one
or the one face of b.) because two. Hence, the the theorea follows.

Schuatically, the iabedding for G' is foraed as shown in Figure 2.3.

As further illustration of the aanner in which the edge adding
technique nay be uployed, we produce an inbedding of the graph G - Ku-x,
wherexisanarbdtrery edgeofKu. Usdo sobybuildingthis graph.
free the conplete graph K3. We begin with the graph K3 iabedded in

”10 “Ge

11

I y. _ \ I U ‘
\ / \
‘ /
’ c i ' $ . . ,

F1 F 3 Single rece'in c'
K Figure 2.3.a

X .

W x“ C ¢ X.

I ‘ / ‘e
I I ‘ /
\ \ ‘ I

. J ,

5% at ’ ”h

- Two faces in G'
Fl F3 Figure 2.3.b

Figure 2.3 Illustration of the Ego Adding Technique

Let K3 be inbedded in the plane and isagine its inside face and

its outside face each consisting of directed edges as follows:

 

 

we add e vertex, labeled it, end the edge (1.1+) so thet both the directed
edge [1,14] and the directed edge [Ml] are in the outside faces

 

12
He now add the edge (4,2) in such a way that the resulting graph
has only one face in the new iabedding. (That is, the inside and
outside faces becone one. be are using the edge adding technique with
the vertex 2 appearing in the inside face and the vertex it appearing
in the outside face.) The final result of this edge adding is shown

in Figure 2.4.

 

 

 

Figure 2.1+ K3 with a Vertex and Two Edges Added.

The edge adding technique will prove useful in finding the naxiaua
genus of graphs whose maxim inboddings have exactly one or two faces.
One can build such graphs by adding one edge at a tine to a subgraph
which is of the same type. Such a building procedure often sakes a
difficult problem more amenable.

The edge adding technique was first aployed by Nordhans, Stewart,
and white [10] as e proof technique in one of their theoreas. It
wasn't until closer scrutiny that we discovered its generalisation
to the technique as stated above. This technique is sonetiaes referred

to as the “ribbon" technique.

CHAPTER 3
A SURVEY OF KNOUN RESULTS

In this chapter, the known results concerning iabeddings of graphs
are given. In addition we give the known genus ferrulas as well as the
known nariaun genus fornulas fer these graphs which are discussed in
this thesis.

All Z-aanifolds upon which graphs are iabeddod are considered to
be compact orientable 2-nanifolds. For this reason, the following
characterisation theorem is neat important:

Classification Theorems [8] A compact orientable 2-nanifold is honeo-

norphic to a sphere or to a connected sun of tori.

The genus of a compact orientable Z-nanifold is the number of
connected tori of which it is the sun. [8]

Throughout this thesis we will use the word "surface” to refer
to a compact orientable 2-aanifold. A surface of this type say be
thought of as a sphere or a sphere with handles. The genus, Y, of such
a surface is then the nuaber of its handles.

As indicated in the last chapter, the iabeddings considered in
this thesis will be Z-cell inbeddings on such surfaces. He will call
such iabeddings cellular inbeddipgg.

The well known Euler Polyhedral for-ula can be generalized to the
following theorea about cellular iabeddings of graphs on a surface.

13

1h
Euler's Theorem: Let F be the number of faces into which a surface of
genus Y is separated by a cellular imbedding of a graph G, where V and
E are the number of vertices and edges of G, respectively. Then

F+v-E+2qu

It is necessary to emphasize that we are making certain assumptions
about our graph G. It is assumed that G is finite, connected, un-
directed, and has no loops or multiple edges. The fact that we are re-
stricting ourselves to cellular inbeddings makes Euler's formula appli-
cable.

The following two theorems concerning ordinary genus are both
important and helpful.

The first theorem, due to Battle, Harary, Kodana, and Youngs [1]
reduces the problem of the genus of a connected graph to that of finding

the genus of a block.

Theorem: If G is a connected graph having k blocks Bl’°"’Bk’ then
K
v(G) -.Z;Y(Bi). Furthermore, in any minimal imbedding of c,
1:

FG - l - k + FB , where FG and F5 denote the number of faces for

i i
G and for B respectively.

1
The following famous theorem of Kuratowski [7] completely character-

izes planar graphs:

Theorem: A graph G is planar if and only if G does not contain a sub-

graph isomorphic, to within vertices of degree two, to either K5 or K3’3.

There is no such characterization for graphs of higher genus. How-

ever, in 1968, Vollernaus [1“] stated that the set of exceptional graphs

15
(corresponding to KS or 18,3) is finite for any sphere with a prescribed
number of handles. Nothing flirther has been established on the subject.
We now list the known genus formulas for graphs which we consider.
In 1965 Ringel [12] showed that Y(Kp,q) - {Kg-73%;?)- , where the
minimum imbeddings produced have quadrilateral faces (with at most one
exception). In 1968, after considerable effort, Ringel and Youngs [13]
established that

Y<Kp) - {mg-(2&3 '

This result settled the famous Heawood nap coloring conjecture in
the affirmative. The genus formulas for the generalized n-cube and
certain special cases of the complete tripartite graph have been dis-
covered by A. T. White [16] . However, such graphs are not considered
in this thesis.

He now turn our attention to the results concerning maneu- genus
which were discovered prior to this thesis. The first result does not
pertain only to maximum genus. However, it was instrumental in inspiring
the concept of maximum genus, and such considerations by Duke led to our
definition [a] .

Theorem: If there eldst cellular imbeddings of the graph G in orienta-
ble zrmnifolds of genera m and n, then for any integer k, mé k4 n,
there exists a cellular imbedding of G in the orientable 2-manifold of

genus k3

Once the maximum genus and the ordinary genus of a connected graph
G are known, the above theorem completely determines all orientable

2-manifolds upon which G has cellular imbeddings.‘

16
The next few theorems are all contained in the paper [10] which
introduced the concept of maidmmm genus.

Theorem: A connected graph G has a cellular imbedding in a surface Sk'

of genus k, if and only if y((:) 4 k4yM(G).

We new list some theorems which establish some bounds for the

maximum genus of a connected graph.

Theorem: If H is a connected subgraph of a connected graph G, then

Gore : If G is a connected graph with v(G) - 1, then YH(G)>2.

The next theorem insures that the maximum genus of a connected
graph is always finite. The fact that the definition of cerium genus
only considers cellular imbeddings is of utmost importance. In fact,
without such cellular considerations, a theorem similar to the next

one simply does not exist.

Theorem: An upper bound for the maxim genus of an arbitary connected

2
imbedding has one or two faces according as B(G) is even or odd, respec-

graph is given by YM(G)_4 [m] . Equality holds if and only if the

tively.

A connected graph G is 2229!. imbeddable if 71:“) - [‘18(G)] .

The inequality stated in this theorem can be arbitrarily inaccurate,
as the following graph Gn shows. It is clear that %B(Gn) - n, but as
we will see later, yum“) - o.

1?

 

Figure 3.1 Two Graphs which are not Upper Imbeddable.

The second graph G of Figure 3.1 shows that the inequality of the
last theorem may be strict, even for blocks, since vn(c) - 1< [§3(G)] - 2.
As we stated earlier, it is quite convenient that the genus of a
connected graph is the sum of the genera of its components. However, as

the graph H below illustrates, such is not the case for maximum genus:

Yum) - 1 f o + o - Yn(triang1e) + Yu(triangle).

V

Figure 3.2 Thetrraph H
be do, however, have the following inequality.

Theorem: If G is a connected graph with blocks Hi' i-l,...,n, then

(-1

Core : If G is a connected graph with n blocks H1, i-l,...,n, then

Zvfififisvfic): [%B(G)] .

18

Corollg: If G is a cemented graph with 1: blocks H , such that

i
maxi) - i803). 1-1.m.n. than yum) "gYHWfl - him).

This thesis extends this last theorem in the sense that it discloses
some more cases in which the mamum genera of the blocks may be added
to obtain the maximum genus of the graph.

The following theorem is the only maidmum genus formula known prior
to this thesis: [10]

Theora: The maximum genus of the complete graph on n vertices is given
by the formula,

yuan) - [t(n-1)(n-2)] .

The following theorem of Duke [it] is often useful in deter-lining
that a certain imbedding is not a maid-um imbedding. It is helpful to
note that an imbedding is maximum if and only if the number of faces
in the imbedding is a minimum.

Theorem: Let G be a connected graph with an imbedding T and b a. vertex
of G. If there is a vertex 3 of G, which is adjacent to b so that
[a,b] is in one face, [he] in another face, and b appears in a third
face, then G has an imbedding with two fewer faces than the imbedding
T had.

CHAPTER h
THE MAXIMUM GENUS OF CERTAIN PLANAR GRAPHS

This chapter will determine the maximum genus of four major classes
of planar mphs. The wheel graphs, the standard maximal planar graphs,
the ”rounded" ladder graphs, and the regular polyhedral graphs are exam-
ined. Hith the exception of the finite class of regular polyhedral
graphs, each of the above classes contains gaphs with arbitrarily large
maxim genus.

A possible conjecture which occurred rather early in the study
of maximum genus is also settled in the negative by these planar graphs.
Is it possible that the maximum genus of a graph is somehow limited by
the magnitude of its ordinary genus? Since the classes of planar graphs
studied in this chapter contain graphs of arbitrarily large maximum
genus, this question is clearly answered in the negative.

All of the graphs examined in this chapter are upper imbeddable.
This need not be true for planar graphs in general, however. Theorem
5.11of Chapter 5 presents an infinite number of planar graphs which
are not upper imbeddable.

The maxim genera of the above listed graphs are given in a series
of theoras. The proofs of the theorems offer good examples of the appli-
cation of muonds' technique and of the edge adding technique. A

By the wheel graph on n vertices, né ‘5, we mean in - [(1 + cn-l’
where the addition means that each vertex of the one graph is joined

19

20
to each vertex of the other. The cycle with n-l vertices is represented
by Gn_1 and the complete graph with one vertex by K1. He label Uh as
the following diagram illustrates:-

“is“
6’:

As is customary, we let E be the number of edges of In.v the number
of vertices, and B the Betti number. Then for the wheel graph, we

have: 3 - 2n-2, v - n, and B - n-l.

Theorem»b.l: The maximum genus of the wheel graph "n on n vertices

is given by the formula:

%(n-2) if n is even.

yuan) - [sup] -
é-(n-l) if n is odd .

2:22;: We use Edmonds' permutation technique. The permutations

we employ may be schematically represented in the following manner:

2" 2c:- I
z>’/~ 22.! 2t-2 2‘
24,)
K. n.

Precisely, the permutations which we use are: (addition mod(n-l))

Bu! (1 2 3 ...n-1).

Pa' “2““ n ‘21-“) {3113;138:3523 :22?

- 1-lpeee' if n 13 Ovang
1hinl' ((21 2) n 21) i-l,...,inn --1) if n is odd.

21
Since the Betti number is odd when n is even and even when n is odd,
'n will be upper imbeddable if we exhibit a two face imbedding when
n is even and a one face imbedding when n is odd. He consider the cases
n even and n odd separately.

gggg;;t Let n be even

We show that the above listed permutations give an imbedding having
two faces: one face has 23 - 8 directed edges, the other has 8 directed
edges.

For the first of these faces (orbits), we begin with the directed
edge [1,2] and trace its orbit. The orbit begins -l-2-3- and there
then follows a section of the crbdt best given by an iterative process.
We indicate the orbit as -l-2-3-L and proceed to describe that section
of the orbit indicated by L. The section L is gotten by placing
J-2,3....,§o-l into the following ooh-o, each mom a; 3 put into the
iteration following J-l and preceding 3+1, noticing that the end of the
scheme for J-jo is the beginning of the scheme for J-jo+l. The scheme

is:
~n-2J-(2J-1)-(2J-2)-n-(2J-1)-2J-(2J+1)-n- .

We first notice that since J/l, the permutations as given do indeed
describe this scheme. We remark that it was very important to begin

with 312, however. The section of the scheme -(25-1)-(23-2)- n- is
dependent upon 23-2 being even. Remember, however, that addition is

done modulo (n-l). Consequently, were 3-1, then 25-2 - o ‘2 (n-l)(a'od(n-l)),
and in the case we are considering, (n-l) is odd! The scheme does

appear as part of the orbit for J-2,...,§n-l. Notice that p n(23+1) -
(23+2) and thus j-Jo is clearly followed by j-Jo+1 in the scheme.

22
Also notice that n appears only when explicitly shown in the scheme
written above.

We now devote our attention to showing that all directed edges
given in L are distinct. We consider the possibilities of an odd nua-
bered vertex appearing in the same edge twice and an even numbered
vertex doing so separately. He begin by considering an even number
k, Zékén-Z. Then R either appears as sose Zjo or Zjl-Z, for some jo
or jl. He consider these possibilities.

If k-Zjo, the possible directed edges in L where k might appear

are:

[mk]; [k,(k-l)]; [(k-l),k]3 [k,(k+1)].

If k-Zjl-Z, we have the following possible directed edges in.L:

[kt-1,14: [km] ,

Since none of these directed edges is the sane, no even number
appears in a repeated directed edge.

Thus, the only possibility for a repeated directed edge is one
involving an odd numbered vertex. Then the odd number r is of one of

the forms r-ij-l or r-233+l. The possible directed edges, then, are:

[n,r] and [r,n],
Thus, no directed edge appears more than once in L.
We now count the total number of directed edges used in L. For‘
each j used in L, 8 directed edges are introduced. (Recall that the

last ”n" for J is also the first ”n” for 3+1.) Hence, the number of

directed edges in L is: sen-2) - lm-l6.

23

Notice that the orbit beginning with the directed edge [1,2] tor»
minates with j-tn-l placed in the schemes 2(én-l) + l - n-1 and we
have pn(n-l) - 1 and p1(n) - 2. Thus, with the exception of the directed
edges represented in -1-2-3-, all the directed edges in the orbit are in
L. Hence, the total number of directed edges in the orbit we are enu-
merating is: (unpl6) +.u -1hn - 12 - 2E - 8. Hence, the imbedding has
yielded one face of length 2E - 8.

Since jfl in the scheme displayed in the face above, the directed
edge [2,1] does not appear in the face. He now trace the orbit in which

this directed edge appears. Using the permutations as given, we have:
-2-l-(n-l)-(n-2)-n-(n-l)-l-n-.

Thus, this orbit contains 8 distinct directed edges. He now have two
faces in our imbedding, one of length 2E~8 and the other of length 8.
Hence, the number of directed edges used in both faces is 23. However,
this is all the possible directed edges of "n and consequently the in-
bedding has exactly these two faces. The case for n even is now com-
pleted.
9592 II: Let n be odd

This case is much the same as case I with one very notable exception.
If we consider the iteration scheme L as given in case 1, we notice that
the problem described there for j-l, no longer exists when n is odd.
Hence, we may use the scheme -n-21-(2j-1)-(2j-2)-n-(23-1)-25-(2j+l)-n-
for all J-l,2,...,%(n-l). (Notice that the only possibility for "trouble"
where a necessarily odd number might be even is when j-%(n-l) and for

a necessarily even number to be odd for this same value of 3 when placed

21:
into the expression for Zj. However, 2(%(n-l)) - n-l, which is even,
and 2(fln-l)) + 1 - n, which is odd).

All directed edges in the iteration are distinct just as before
in case I. Thus the total number of edges used in the iterated path
is 8(%(n-l)) - hn - it - 2E. Thus all the possible directed edges are
used in this single face, and flu has an imbedding with one face. The

theorm is now proven.

We next compute the maximum genus of what we call the ”standard”
maximal planar graph with n vertices. The graph may be described as

K2 + Pn-Z' where addition is as described before, K2 is the complete

graph on 2 vertices, and Pn_2

n-3, n _>_ h. We let Mn - K2 + Pu...2 and refer to it as the "standard”

maximal planar graph on n vertices. The graph "n has the following

is a path with n-2 vertices, of length

parameters: E-Bn-6: V-n: 5(Hn)-2n-5. Hedrawhnwithits
planar imbedding as shown below, with the vertices numbered as indicated.

 

 

hon the theorem given in Chapter 3, we see that Yuma) $[gf-i]- n-3.
Consequently, if we can find a cellular imbedding of Mn with two faces,
we will have shown that equality holds in the above inequality. He

have the

W: The standard mafimal planar graph "n has maximum genus n-3.

25
2:22;: Let “n be labeled as in the illustration above. Since
fin - Kfi and since the maximum genus.of ha is later shown to be one,
we assume n 2 '5, He again employ the Edmonds technique.

Let the vertex permutations be as follows:

pl: (2 3 u . . . n)
pz: (1 3 h . . . n)
p3! (4 1 2)

pn! ((n-l) 1 2)

pj: ((3-1) (J+1)1 2)
j. 1+,...,(n-1).

when these permutations are used to trace an orbit we notice the follow-

ing scheme developing:
-l-k-2-(k+l)-k- .

where k - 3,h,...,(n-l). Since pk(k+1) - l, and p1(k) - (k+1), we see
that k - 30 is followed by k - jo + l in the scheme. When k - n-l, we
have -l¥(nél)¥2-n-(n-l)-, which is then followed by -l-n-2-, and since
p2(n) - 1 and 131(2) - 3, the face is completed. The number of directed
edges in the face is 5(n-3) + 3 - 5n - 12.

Because the above schale begins with k - 3, the directed edge [1.2]
does not appear. Thus, we begin with this directed edge and trace its

orbit. Following the direction of the permutations we have:
’1‘2-3" e e e -(n-1)-n- s

Since pn(n-l) - l and p1(n) - 2, the face is completed. Thus we have a

face with n directed edges.

26
The total number of directed edges used in the two faces is then
511-12 4- n - 6n - 12 - 2E. Hence, all the directed edges are used and
"n has a cellular imbedding with two faces. (It is clear that all the
directed edges in each of the two faces are distinct.) Thus, we have

the formula, Yuan) - [%8(Mn)] - n - 3.

It has now become clear that if one is successful, mmonds' tech-
nique provides a very clever way in which to produce cellular imbeddings.
In the next theorem, we use both this technique and the edge adding
technique as described in Chapter 3. The next planar graph which we
consider is the graph which we call the ”rounded” ladder graph.

Let L n - CnXKz, where Cn is the cycle on n vertices (n23).

2

We call L2n the ”rounded” ladder graph on 2n vertices. It has the fol-

lowing parameters: 12 - 3n, V - 2n, 8(L2n) - n + 1.

Theorg 4,3: The maddlnum gains of L n is given by the formula

2
mum) - [%~B(L2n)] - [flnflfl-
1:22;: We use induction on n. The following illustration indicates

the labeling we impose on L :

 

 

 

 

 

 

 

 

 

 

2n
n z 3 T" W
a' z' 3’ (is )' n'

Let n - 3, then 8(L6) - 11». is are thus looking for a one face
cellular imbedding. He use the following persutations at the vertices

Of L6.

27
p1: (2 1' 3)
p28 (1 2' 3)
p38 (2 3‘ 1)
p1.8 (2' 1 3')
p2.8 (1' 2 3')

PBe' (3 2' 1;).

We use these permutations to trace the orbit which contains the directed

edge [1,3] :
-l-3-2-l*l'93'-3-l-2-2'-3'-l'-2'-2-3-3'-2'-l'-.

Hence, all 18 directed edges of L6 are used in this single face. The
imbedding is then the desired cellular imbedding with one face. Our
induction is now anchored.

He now suppose that n - k+l and that the graph L2k has an imbedding
on a surface of genus [%B(L2k)]. The cases n - k+l is odd and n - k+l
is even are most easily done separately.

gg§g_;3 Let n - k+l be an even integer.

Since 8(L2k) - k+l, L

2k
face because it is upper imbeddable by hypothesis and because its Betti

must have a cellular imbedding with one

number is even. L2k is labeled as indicated in the above diagram.
Between the vertices (k-l) and k insert a new vertex "a” on the
edge ((k-l),k). Similarly, insert a vertex a‘ on the edge ((k-l)',k').
Form an imbedding for this new graph by changing the vertex permutations
at k, (k-l), k', and (k-l)‘ and leaving all other permutations as they

were in the imbedding for L

Zk' The changes are made as follows:

28
substitute a for k in pk.»1
substitute a for k-l in pk
substitute a' for k' in p(k_1).

substitute a' for (k-l)‘ in pk,.
and employ the new vertex permutations at a and a':

pat (k (k-1))

Pae' (1" (19'1”).

This permutation scheme now gives a cellular imbedding with one face
for the new graph L2k +ca + a'. He now employ the edge adding tech-

nique to form L from this new graph by adding the edge (a,a').

2k+2
By the theorem for the edge adding technique, we may add the edge (a,a')
in such a way that the resulting graph, L2k*2, has a cellular imbedding
with two faces. Since 8(L2m) - (n+1) + 1 - k + 2, which by assump-
tion is an odd integer, this imbedding has the desired number of faces.

Case I follows by mathematical induction.

Case II: Let n - k+1 be an odd integer.

By the induction hypothesis, L2k is upper imbeddable and has a
cellular imbedding with two faces. is intend to employ the edge adding
technique once again. However, the choice of the edges upon which
a and a' may be inserted must be more judiciously chosen. He must
join two vertices which are in different faces in order to have an

imbedding of L2k+2 with one face. We begin with the

Claim: There is a vertex "a” in L2k such that the directed edges

[a,a+l] and [a+l,a] are in different faces for the cellular

29

imbedding of L with two faces. (where (k+l)El(mod k)).

2k
Proof of Claim: He employ the indirect method of proof. Suppose
that for each vertex b sV(L2k), the directed edges [b,b+l] and
[bi-1J1 are in the same face.

Since not all edges in a particular orbit can be of the £011!
[ 1,1'] or[i',i] , there is a vertex "s” so that [ms-ll] and [z-l,z]
are in different faces, say I" and F" respectively. If we let the
arrows in the following schematic diagram indicate faces, we have

the representation:

 

Zfl

 

By assumption, [2,2-1] is also in F” and [rt-1,2] is also in 1'".
Consequently, the vertex permutation at 2 must have pz(z-l)-z'
because [z-1,z] and [z,z+l] cannot be in the same face. Likewise,
pz(z+l) - 2', since [mi-1,2] and [ms-l] cannot be in the same face.
By Edmonds' theorem, the given imbedding can only be cellular if
the vertex 2' has degree one. However, each vertex of L2k is of
degree three. Hence, we have our contradiction and the claim is

established.

Without loss of generality, we assume that the vertex ”a” of the
claim is one of the vertices whose label is not a primed number. Let

[a', (a+l)' be in some face of the imbedding, say I". By the above

30
claim, the directed edges [a,a+l] and [a+1,a] are in each of the two
faces of the imbedding.

As in case I we insert the vertex b on the edge (a,a+l) and the
vertex b' on the edge (a',(a+l)') and form a new imbedding of this graph
exactly as was done in case I. He then have an imbedding of the result-
ing graph which is cellular with two faces. Furthermore, two faces may
be chosen so that b and b' are in different ones. The edge adding tech-
nique then applies to allow us to add the edge (b,b') in such a way
that these two faces become one. However, when the edge (b,b') is added,
the resulting graph is the graph L2k+2‘ Hence, the graph L2k+2 has a
cellular imbedding with two faces. Since B<L2k+2) - n+1. which is odd,
we have an imbedding with precisely the number of faces desired for the
graph to be upper imbeddable.

By induction, the graph L2n is an upper imbeddable graph for all

natural numbers n. The theorem is proven.

The proof of the above theorem illustrates the manner in which the
Hmonds' technique and the edge adding technique may be employed in con-
junction in order to obtain a desired result.

We now turn our attention to five planar graphs which are histori-
cally important, namely the regular polyhedral graphs. The tetrahedron,
the cube, the octahedron, the dodecahedron, and the icosahedron graphs
are shown with their planar imbeddings in Figure 4.1. I: 11]

We find the maximum genus of these five graphs in the

Theorem “fl: All of the regular polyhedral graphs are upper imbeddable.
Proof: The tetrahedral graph is the graph K“, which is studied

 

 

 

 

 

 

 

Tetrahedron B = 3

 

Dodecahedron B = 11

 

\A

7

‘7

Icosahedron B = 19

The Regular Polyhedral Graphs

32
in Chapter 7. The graph of the cube is L8, and is thus upper imbeddable
by Theorem 01.3.

The dodecahedral graph has a cellular imbedding with two faces
which can be traced using the cyclic permutations indicated in Figure
h.2 (ioe. an arrow at a vertex means that the permutation at that ver-
tex acts cyclically as the arrow indicates).

Both the octahedral graph and the icosahedral graphs are most easily
handled by the edge adding technique, beginning with the innermost trian-
gle. He illustrate the procedure for the icosahedral graph in Figurelh.3.
At each step we add three vertices and the number on the edge indicates
the number of faces the new imbedding for the graph has after that edge
is added. The darkened vertices are those just added. The edge adding
is always done beginning with the new vertex farthest to the left and
adding edges in a counter-clockwise manner about the original figure.

By this edge adding, them, the icosahedral and octahedral graphs are

also upper imbeddable. This completes the theorem.

 

 

 

 

 

 

 

 

Figure “.3 Adding Edges for the Icosahedral Graph

CHAPTER 5
PROPERTIES OF THE MAXIMUM GENUS OF A GRAPH

This chapter will investigate some of the properties of maximum
genus. Three problems of interest are discussed. As was mentioned
in Chapter 3, a major difficulty occurring with computations of maxi-
mum genus is the fact that the sum of the maximum genera of the blocks
of a connected graph C may be less than the maximum genus of C. The
first section of this chapter seeks to give some insight into this
problem.

Since two extreme kinds of genera for a connected graph are defined,
the question arises of finding graphs for which these two genera are
equal. In the second section of this chapter all graphs for which
equality holds are determined.

The third part of the chapter deals with characterizing those
planar graphs whose aaximum genus is one. Such a characterisation theorem
completes the chapter.

He first determine some connected graphs which have the maximum

genus summability property in the

Theorem 5.1: Let Cl and C2 be vertex disjoint connected graphs, and

C - Cl(e)G2 be the connected graph formed from Cl and C2 by adding one

edge e - xy, joining a vertex x in Cl to a vertex y in CZ. Then

yum) - yuccl) + Ynez).

34

35

mo; of Iheorem 5.1: Let Tl be any cellular imbedding of Cl with

permutation scheme P1. The permutation scheme at x is given by

pi: (xi x2...), where xi may equal x2 if the degree of x is one. Let

1‘2 be any cellular imbedding of (:2 with permutation scheme P2. The

permutation scheme at y is given by p3: (y1 y2 ...) where y1 may equal
y: if y has degree one. He may then form a cellular imbedding T of C

1 2
by leaving Pv - pv for v in G1, v f x; leaving pu - pu for u in CZ,» u f y:
then define pxl (x1 y x2 ...) and py! (y1 x y2 ...).

There is a face f' in T with f': -x1-x-x2-(q')- and a face 1’" in

1
T2 with f”: ql-y-yz-(q")-, where q' and q” are just notational con-
veniences to indicate the portion of the faces not explicitly given.
These two faces are combined in T for G into one face given by

f: -x1-x-y-y2-(q”)-y1-y-x-x2-(q')-. This one face uses all of the in-
novations in T as compared with T1 and T2, so all the other faces of T

are the same as faces in T1 and T . Hence we have

2
(l) F(T) - F(Tl) + F(Tz) - 1 ,
where F(s) indicates the number of faces in the imbedding s, s - T, T1,
or T2.

Conversely, if we are given T for G, we reverse the above definitions

and arguments to find ‘1" and T" for C and C respectively, with the

l 2
property
(2) F(T') + F(T") - F(T) + 1.

Suppose T* is a maximum cellular imbedding of C corresponding to

YH(G). Then F(T*) 5 F(T) for every cellular imbedding 1' of 6. Using

36

(2) we know there exists a cellular imbedding (T*)' for G1 and a

cellular imbedding (9)" for (:2 with F(T*) - F((T*)') + F((T*)") - 1.

However, we may also begin with maximum imbeddings of C1 and CZ.

Let T! be a cellular imbedding of C1 corresponding to YH(Gl)’ so

1 of (:1. Similarly,

let T; be a cellular imbedding of C2 corresponding to YH(GZ)' so that

F(Tg) 5 F(TZ) for every cellular imbedding T2 of (:2. Using (1) we know

there exists a cellular imbedding T of c with F(T) - F(Ti) + F(rg) - 1.

that 1"(1‘1') _<_ F(Tl) for every cellular imbedding 1'

By the minimal properties of F(Ti‘) and F(i'g) it follows that
F(T) - F(Tg) + F(Tg) - 1 s F((M') + WM") -1 - F(M.

Should strict inequality hold in the above relation, the minimal property
of F(T*) would be contradicted. Hence equality holds and we make the

following computation:

2Yn(G)-2+E-V-F(T*)
'2+(El+E2+l)'(v1+v2)'(F(Ti)+F(T§)'1)
-(2+E1-Vl-F(T*1*))+(2+E2-V2-F(T;))
'ZYM(Gl) +2YM(<:2).

Division by 2 then completes the proof of the theorem.

ggrg;;§;z_5£g: Let G1, 1 - l,2,...,n, be connected graphs with all of
the (:1 pairwise vertex disjoint. nerine o - Gl(e1)62(e2)63(e3)...
(en_2)cn_1(en_1) on, where e1 - xixi +1 is an edge joining x1561 to

e(} Then

xii-l i+1‘

YM(G) - 1211/1461).

37
M of Corolla 5.2: is use induction on the number of con-
nected graphs n. The case n - l is clear and Theorem 5.1 makes the

induction step.

We now turn our attention to connected graphs composed of blocks
which do not have K2 so conveniently located. Let Cl and G2 be two
connected graphs which share exactly one vertex. We intend to deter-
mine the conditions necessary in order to add the maximum genera of
these two graphs and obtain the maximum genus of the newly formed mph.

We begin with a lemma.

1,“: Let T be a cellular imbedding of a connected graph G such
that there is a vertex c of C which is contained in the boundary of at
least two faces of the imbedding T. Then in G there exists a vertex
b, which is adjacent to c, such that the directed edges [b.c] and [c.b]
occur in different faces of T.

my Let V(c) denote the set of vertices of G adjacent to c,
and let I" be a face of T containing c in its boundary. We define

V' ; V(c) as follows:

v' -2x 6 V(c)

either [no] or [on] is in F“ 3.

 

Then V' f fl since c is in F'.

If V' - V(c), let [y,c] be a directed edge in some face F” f F';
by assumption, such a vertex y exists. Then y e V(c) - V', and thus
[my] is in F'. Thus, y is a vertex of the desired kind.

Assume V' % V(c). Let pc be the vertex permutation at c of the

permutation schue corresponding to the imbedding T. By Edmonds' theorem,

38
p c is a cyclic permutation. Hence, there is a vertex x06 V' so that
O O O
pc(xo) f v , Thus, [c,pc(xo)] ,«f F and hence [x°,c] ,v‘ r .
Since xo 5 V', we must then have [onto] 6 1". Thus xo is the

desired vertex.

111g: 5.48 Let T be a cellular imbedding of a connected graph G.
Suppose there is a vertex c of G which is contained in at least three
faces of T. Then there is a cellular imbedding T' of G which has two
fewer faces than the imbedding T.

M: By Lemma 5.3, we may choose two faces of T, 1'" and F",
along with a vertex b £V(c), so that [b,c] 6 F' and [c,b] c 1'”.

However, by hypothesis there is a third face I" in which c is al-
so contained.

The vertex c and the faces 1““ ,F”,F serve to make the imbedding T
satisfy the hypothesis of the face reduction theorem of Duke discussed
in Chapter 3.

Hence, by that theorem, G has an imbedding with two fewer faces

than T.

(balm 53' 5: Let T be a maximum cellular imbedding of a connected
graph G. Then there is no vertex of G which occurs in the boundary
of more than two faces of T.

M: By the theorem a vertex contained in three or more faces
would permit an imbedding with fewer faces, so the imbedding could not
be maximum

In order to facilitate the statement of the next theorem we intro-

duce some additional notation. Let c be a cutpoint of a connected mph

39
G. Us m _G_ at 9_ into 23.9. connected m 91 and 92 as follows:
Let H1 K
am integu 1 g k 5 m. Let c1 - it), Hi and G2 {Quay whue we intend for

, i - 1,...,m, be the blocks of G which contain c, and let k be

the union to be done so that the blocks of both 61 and 62 share the

vutex c. G is said to be semted at 2 into the connected graphs

61 and 62. We are now prepared to state the theorem.

Theoru 5.6: Let G be a connected graph which is separated at a cutpoint

c into two connected graphs Cl and G Let T be a cellular imbedding

2' i

of (3'.1 having M faces, 1 - l or 2. Suppose c is contained in at least

1

11 faces for each of T1 and T2,

thus is a cellular imbedding of G with H1 + H2 - (2n - l) faces.

whus n is a positive integu. Then

m: is first note that n g 1. Let P1 and P2 be the Edmonds‘

perentation schemes corresponding to '1‘1 and T2 respectively. Suppose

that one of the n faces, F1, chosen from T1, is of the form

.4. [tag] [4,4], 1 - 1 or 2.

we mean for the notation to imply that _tgg faces have been chosen, one

from the imbedding T the other from the imbedding T The vutex

1' 2'

pumutations pi, i - l or 2, can be written:

P]" (I: see Xi), Pi! (I: see Xi).

C

Us form an imbedding T of G as follows:

1
Px -pxifx£V(Gi),x;‘c,i-lor2

pc: (é ... xi'é ... xi).

40
Then the faces F1 and F2 become one face in this new imbedding of G,
1 and T2 are now faces of T.
The 2n faces containing c which were originally chosen from T1

while all other faces of T

and T2 new number only 2n '- 2. He also have the above new face con-
taining c. Hence, we now have c contained in at least 2n - l faces of T.

If n - 1, the above work completes the proof. If n 2 2, then
(2n ; l) _>_ 3, and the T formed above is an imbedding for which c is
contained in at least 3 faces. By Theorem SJ», G has an imbedding T"
with two fewu faces than T. It is clear that if thus are now three
or more faces of T* in which c is contained, we may again reduce the
numbu of faces in an imbedding of G, by again applying Theorem 5.1+,
this time to T*.

The question now becomes that of knowing how many times such a
reduction of faces can occur before we obtain an imbedding of G for
which c is contained in fewu than three faces. He cannot determine
the exact numbu of times such an occurrence can happen. Howsvu, we
do establish the claim which follows.

1139;: He may apply Theorem 5.10, to reduce the numbu of
faces in an imbedding of G, at least n-l times.

Mof of Claim: Suppose we apply Theorem 5.4 the first time
as shown above: i.e. aftu two of the chosen 2n faces have been
combined into a single face. The imbedding T still has the othu
2n-2 faces which we originally chose from T1 and T2. In addition,

T has the face which combined F1 and F2. Hence, c is contained in
at least 2n-1 faces of T.
Now suppose we have done a reduction, using Theorem 5.1+, k

times. Each such application results in the loss of two faces in

lbl
which c was contained. Us need only ask how large k may be and
thus still be at least 3 faces containing c in the new imbedding.
we need the inequality (2n-1) - 21: _>_ 3 to be true in ordu to reduce
at least one more time. (i.e. (Zn-#1) is the largest possible num-
bu of the originally chosen 2n faces which we may have used; it
is possible that we haven't used this many of these chosen faces,
since some of the reductions might have involved faces which were
not among the ones originally chosen). The above inequality is
true as long as k 5 (n-Z). Thus, we can safely apply the reduction
of faces theorem n-2 times and still have c contained in at least
three faces of the last imbedding obtained.

Under these circumstances, the reduction of faces theorem may
be applied at least one more time. Thus, we can safely apply the
Theorem 5.1; at least (n-1) times. The claim is established.

We now count the total numbu of faces which have been lost from the
and T by these (n-l) applications of Theorem

1 2
5.1}. Two such faces wue lost each time the theorem was applied. Hence,

original 111 + 142 faces of T

repeated applications of the theorem resulted in the loss of 2(n-1)

faces. However, one face was lost before such applications of the theoru
wue begun. Hence, we have lost a total of 2n-l faces. Thus, we have
obtained an imbedding of G which has M1 + H2 - (Zn-1) faces, as desired.
This completes the proof of the theorem.

is now give some corollaries which give insight into the problem
of adding the maximum genera of two connected graphs which share a
single vertex. An important consequence of these corollaries is to

notice that whether or not one can add the maximum genus of two such

1+2
graphs is in one sense dependent upon the differences [*9 (G1)] - Yllmi)

for the two graphs G1 and G2, 1 - l or 2.

Corollary 5,2: Let G be a graph as described in Theorem 5.6, with each
of the T1 a maximum imbedding, 1 - l or 2. Then “(6) 2 714(61) + .
YH(G2) + (n-l).

2522‘.) Let T1 and T2 in the theorem be imbeddings on compact or-V
ientable nuirclde er genus “(01) and “(62) for the graphs c1 and (:2
respectively.

Using Euler' s formula and the following inequality derived from

more. 5e6'
we obtain the desired result.

W: Let G be a connected graph with a cutpoint c. Suppose
that when G is separated at c, the separation is done in such a way that

both G1 and 62 are upper imbeddable. Further, suppose that if 8(61) is
odd, thencis involvedineaohefthetwofaceeofthemeximumimbedding
for G1, 1 - l or 2. Then G is also an upper imbeddable graph.
M: If either of the Betti numbers for the two graphs GI and
G2 is even, then the theorem gives a cellular imbedding with either
one'or two faces, depending upon the parity of the other Betti number.
In either case, the graph G is upper imbeddable. ‘
SupposethstboththeBettinumbersereodd. Thenweplacen-iz
into Corollary 5.7 to obtain the inequality yum) a Ylml) + “(62) + 1.
However, since both Betti numbers are odd, the following relation holds:

43
[we] - [%(B(G1) + a(c2))] - [imp] +[ts<c2)] + 1.
Since G1 and G2 are both upper imbeddable, we have the inequality
7,,(6) S YH(G1) + YM(G2) + 1, from the uppu bound proputy of maximum

genus. Hence, the corollary is established.

its are now in a position to give a necessary condition for the max-
imum genus of a connected graph to be the sum of the maxim genus

of two connected graphs into which it is separated.

T‘hmem 5.2: Let G be a connected graph which is separated at a cut-
point e into two connected graphs G1 and G2. If YM(G) - Yu(Gl) + YH(G2),
then eithu G1 or G2 has a maximum imbedding in which o is contained

in exactly one face.

M: He prove the contrapositive of the theoru. Suppose that
all maximum imbeddings for both G1 and G2 have c involved in two faces.
is then place n - 2 into Corollary 5.7 and obtain the inequality
YH(G) 2 “(61) + “(62) + 1. This disallows the possibility for summing

the maximum genera, and the theorem is completed.

He now present a corollary which is just a special case of Theoru
5.9. Howevu, since strongly regular graphs are becoming evu more
frequently studied, we state the corollary.

Go .10: Let G be a connected graph which separates at a cutpoint
c into two strongly regular graphs G1 and G2. If YH(G) - “((61) + Yuma),
then eithu G1 or G2 is uppu imbeddable with even Betti numbu.

M: If both G and G have at least two faces in their maximum

1 2
imbeddings, then some vertex is contained in two faces. Since all the

ha
vertices of a strongly regular graph have exactly the same adjacency
properties, the vertex c may be considered to be that vertex. Corol-
lary 5.7 would then apply to destroy the possibility for summahdlity.

is neat turn our attention to the determination of those graphs
whose maximum genus and ordinary genus are equal. He first define two
very special graphs, which play an important role in the characterisa-
tion theorem which follows.

The graph H is the graph which is obtained from the wheel graph
'5 by deleting a one factor from C . The graph Q,is a graph to which
Ké,3 is homeomorphic (i.e. K2,3 is isomorphic to a subdivision of Q.)
Figure 5.1 illustrates the two graphs.

A.ga§tg§_is a connected graph each of whose blocks is either a cycle

or K2.

H I Q
Figure 5.1 The Graphs H and Q

Theorem 5.11: Let G be a connected graph. Then the fellowing state-
ments are equivalent:
1.) 7,,(6) - Y“)
11.), G does not contain a subgraph homeomorphic to either H or Q.
iii.) 6 is a cactus all of whose cycles are vutex disjoint.

in) yum) - we) - o.

45

5221 of Thggrem 5.11: is use the circular set of implications
1.)=>1i.)=:>111.) =>1v.)=>i.).

i.) 211.)

The proof of this portion of the theoru can be found in the papu
by Nordhaus, Ringeisen, Stewart, and White. [9]

ii. =>iii.

He first show that undu condition 11.), the graph G can have no
blocks which are not cycles. Secondly, we show that the condition
forces all the cycles of G to be pairwise vutex disjoint.

Let B be any block which is not a cycle. Us show that B contains
a subgaph which is homeomorphic to Q. Let a and b be any two vutices
of the block B. By a well known proputy of blocks, thus is a cycle
G through a and b. Since we are assuming that B is a block which is
not a cycle, thus is at least one vutex of B which is not on C. Conse-
quently, thus is such a vutex, call it d, which is adjacent to a vu-
tex on G, which we name c (see Figure 5.2). By a charactuisation of a
block, thue is a cycle, say Cl, which contains both the undirected edges
(c,d) and (k,c), whue k is some vertex of c which is adjacent to c.
Then G and c1 are cycles which share at least one edge. Hence the graph
composed of these two cycles contains a subgraph homeomorphic to Q,

contrary to the assumption 11.).

Figure 5.2 Obtaining the Graph Q

#6

Thus, G can have no block which is not a cycle or K Hence, G

2.
is a cactus.

Suppose further that G now contains two cycles which share a verb
tex. Clearly, G then contains a subgraph which is homeomorphic to H,
contrary to condition 11.).

Consequently, G is a cactus all of whose cycles are disjoint.

iii. iv.

Since G is a cactus all of whose cycles are disjoint, G is clearly
a graph of the kind described in Corollary 5.2. We let each of the G

i

in this corollary be either a cycle or K We can then coapute the

2.

naximun genus of G by adding the maxiaua genera of the G Since the

1.
Betti numbers of all such blocks are zero, YH(G) - 0. Because the
aaxiaua genus of a connected graph is always at least as large as the
ordinary genus, the ordinary genus of G is also zero.

lid-=21 .)

This is an obvious iaplication.

By the circular nature of our proof, the theorem is proven, and

all the above statements are equivalent.

We now introduce some notations and definitions, along with some
theorems concerning them. Although the graphs defined are theaselves
of interest, our purpose in introducing them now is to lead ultiaately
to the characterization of graphs whose narimua genus is one. we de-
fine various graphs which we shall call chain graphs, butterfly graphs,
and rose graphs.

Letheaconnectedgraph. heflmfififlgmgfi

_c_ is defined inductively, and denoted cn(c), where (21(G) - c. To define

#7
02(G) frca 01(G), choose two not necessarily distinct vertices of 01(G),
a and b. Fbra 62(G) by adding a path from a to b. To avoid loops or
multiple edges, if a - b, we insist that the path be of length at least
three; if a and b are adjacent the path must be of length at least two.
To define chum) froa ck(c), k g 2, we choose two not necessarily dis-
tinct vertices of Ck(G), which were not vertices of Ck_1(G). Add a path
between the chosen vertices, subject to the same restrictions on length
given when forming c2(c) from °1(°)' Figure 5.3a gives sons examples
of chain graphs.

The buttufly E29. with g m is denoted Bn' It is formed by
‘beginning with nontrivial path P of any length and adding n pairwise
vertex disjoint paths of arbitrary length between the endpoints of P.
In order that Bn not be a nultigraph, we insist that not mere than one
of the nil paths (including P) be of length one. Figure 5.3b gives
some exaaples of butterfly graphs.

The Iggg,g;§ph_gith,g;pgtalg is the graph obtained by attaching
n cycles to a vertex b, in such a way that no two of the cycles share
lore than the vertex b. A rose graph with n petals will be denoted by
Rn. Figure 5.3c gives some examples of rose graphs.

Us first reaark that all the buttufly graphs and rose graphs are
planar. Furtheraore, the chain graphs have the sane genus as that of
their particular base graph. To see this one need only imagine adding
the new path of ck+1(G) within a face of Ck(G), an operation which
leaves the genus unchanged.

Furthsr*notice that if one uses the theoreas and corollaries of

the earlier portions of this chapter, one can find the maxi-us genus

#8
of a graph which is a combination of chain, rose, or buttufly graphs,
by knowing the nximn genus of these basic graphs. is thus turn to
the task of finding the maxim genus of these newly defined graphs.

A ‘.

C’MKV) C3 (:2. ’v’ocyc’!)

Figure 5s33

83 Figure 5.3‘b

O 0
' O
R

R2

3
Figure 5.3c

Figure 5.3 Three New Kinds of Graphs

Ma Let G be eithu one of the two graphs 32 or B2. Then
YH(G) - 1. (Notice that if K is any cycle, we have B2 - 62(K).)

Ms fish of the two given graphs have Betti mnbu two. Hence,
by the uppu bound theorem, each has aaxiaua genus no largu than one.
mus, we display cellular iabsddings of each graph on the torus and con-

plete the proof.

“9

An iabedding for 32 is:

 

 

 

 

 

 

An iabedding for B2 is:

 

\V

 

 

 

 

 

 

v

Notice that each of the two iabeddings is indeed cellular.
The next two theorems will detumine the maximum genua of the
buttufly graphs, the rose graphs, and sons chain graphs.

Thmg 5.13: Let G be an uppu imbeddable graph. If 8(G) is odd,
fora c2(c) fro- cl(c) - c by adding a path between two vutices of c
which occur in two different faces of the namua cellular imbedding
of G. Then ck(c) is uppu imbeddable for all k.

M! Us use mathematical induction on n, the length of the
chain graph. Notice that 8(Cn(G)) - 8(G) + (n-l).

If n - 1, then the chain is only the base graph itself, which is
assured to be upper imbeddable. If n - 2, then c2(e) is upper inbsd-
dable because the edge adding technique may be applied to give eithu a
one (if 8(G) was odd) or a two (if B(G) was even) face cellular imbed-
ding of c2(c).

Suppose that amr chain graph of length It is uppu inbeddable and

let G be a chain graph of length k+l, whue we are assuring that k-I-l Z 3.

50
He eaploy the edge adding technique and the argunent is done in two
cases. Without loss of generality, assure that B(G) is even.

m: Assume k+l is even.

Gonsidu the chain graph (3' of length I: with base G, which is
a subgraph of G. This mph diffus from C only by the lacking of the
path which was added to form C from C'. By induction, 0' is an uppu
imbeddable graph. Because k is odd, and because 5(0') - (k-l) + 5(6).
0' must have a cellular iabedding with one face.

The procedure now becomes clear. He add the path needed to fern
G in such a mannu that C obtains a two face cellular imbedding from
the one face cellular imbedding for (2'. Because a path may be obtained
by adding an edge and then inserting vutices of degree two on the path,
the iabedding problea can be regarded as that of adding an edge. That
the desired imbedding is obtained is guaranteed by the edge adding
technique. Hence, C has a cellular imbedding with two faces. Case 1
is coapleted.

M: Assume k+1 is odd.

Let G' be the chain graph as defined in Case 1. Considu the chain
graph G" of length k-l with base G which is a subgraph of G'. G” then
has even Betti numbu, since 3(c”) - (k-Z) + 6(6).

Fun 0' from G" in a nannu analogous to that used in Case 1 to
form C from C'. By the edge adding technique, each edge of the newly
added path has its two directed edges in diffuent faces of the two face
cellular imbedding of (3'. Us form C from G' as was done in Case 1..
Because the endpoints of the path to be added may be considued to be
involved in diffuent faces, the path may be added so that a cellular

51
imbedding of C with one face results. Thus, C has a cellular'imbedding

with one face and Case 2 is completed.
The proof is completed when we realize that if the base graph would
have had odd Betti numbu, the proofs of Cases 1 and 2 would have been

revused.

The theorems for the rose and buttufly graphs are done similarly.
The two kinds of graphs are similar enough in their structure that we

find their maximum genua simultaneously in the

111212 5.11“ The rose and buttuf'ly graphs are uppu imbeddable.

1:22;: We use induction of n, the nunbu of petals (wings) which
the given graph has.

Lemma 5.12 establishes the result for n - 2 and the case n - 1 is
a cycle and is thus uppu imbeddable.

The induction argument is done in two cases and exactly as was
done in the proof of Theorem 5.13. Consequently, we do not give an
flirthu details of the argunent hue.

He now put these theorem to use in charactuizing those connected
graphs which have maxim genus one.

Since naximum genus and genus can be equal only when both are sue,
graphs of maximum guns one must necessarily be planar. (Theorem 5.11).

One will notice in what follows that we have made frequent use of
what we have learned concuning the structure of graphs of maximum genus
zuo. He would also hope that graphs with maxim genus one would have
a relatively simple structure as did those of nautimun genus zero.

52
The procedure which we follow is to introduce and prove sevual

lenses, and to then suamarize their results in a charactuization
theorem.

Graphs of maximum genus one are first charactuised to within
blocks of maximum genus one. Some comments concerning blocks of max-
imum genus one are then made to complete the chaptu.

Throughout what follows, a nonmvig $993 will be any block
which is not the mph K2. Corollary 5.2 allows us to confine our study
to such blocks.

Ma Let c be a connected graph with yum) - 1. Then G has
at most one nontrivial block.

mg: is use a proof by contradiction, by supposing that G has
more than one nontrivial block.

Since any such block must contain a subgraph of the form of a
2-winged buttufly, B2, Lemma 5.12 applies to yield that such a block
must have nximun genus at least one. Since the maxim genus of a
connected graph must be at least as large as the sun of the aaximm
genua of its blocks, the maximum genus of G would have to be at least

two. We have our contradiction, and the lemma follows.

He find it necessary to define the nontrivial multiplicity of a

cutpoint of a graph. The nontrivial multipligm g; g m g,
denoted n(c), is the numbu of nontrivial blocks in which c is contained.

M: Let G be a connected graph with YM(G) - 1. Then the fol-
lowing are true:

i.) For aw cutpoint c of G, m(c) _<_ 3.

53
ii.) If c is a cutpoint with m(c) - 3, then each block at c is

a cycle. Furthermore, no other cutpoint of G has nontrivial
multiplicity larger than one.
2:22;; Suppose that G has a cutpoint whose nontrivial multipli-
city is at least four.
By a well known theorem about blocks, c must be involved in at
least one cycle of each of the blocks of which it is a vertex. Hence,
G has a subgraph which is a rose with four petals, 3”. However, Theorem
5.1“ then applies to give YM(Hu) - 2. Since Bu is a subgraph of G, we
must then have that vM(G) 2;2, a contradiction. Hence, 1.) is proven.
How suppose that c is a cutpoint with nontrivial multiplicity three.
Let one block B containing c be a graph which is not a cycle. Lemna
5.12 implies YH(B) 2;l. The cutpoint c is contained in a cycle for
each of the other two nontrivial blocks containing c. These two cycles
may be described as a rose with center c and with two petals. This
graph 82 has been shown to have maximum genus one. Let G' be the subs

graph of G composed of R2 and B, sharing the cutpoint o. By Corollary

5.7 we have vM(c') .>_ m(B) + “(32) z 2. Since m(c) a “(6'). this
is a contradiction. Hence, each block at this cutpoint is a cycle.

Now further suppose that there is some other cutpoint of G which
has nontrivial multiplicity at least two. Let c' be one such cutpoint
so that d(c',c) - flip d(c,k), where d(x¢y) is the distance in G between
two vertices of G and k is any cutpoint with nontrivial multiplicity
at least two.

Then either c and 0' share a nontrivial block or they do not.

Case 18 Suppose c and c' share a nontrivial block.

9+

Because c has nontrivial multiplicity three, this shared block
must be a cycle. Since c' is involved in at least one other nontrivial
block, G has a subgraph which can be regarded as two roses R2 and 3;
sharing the vutex c, as the following illustration shows.

 

By Corollary 5.7 we have m(c) z YM(RZ)+YH(B2), a contradiction.

m: Suppose c and c' do not share a nontrivial block.

Again we carefully choose a subgraph of G. Notice that c and c'
must in this case be joined by a path of blocks all of which are copies
of the graph K2. Thus is a subgraph H3 at the vutex c and a subgraph
Hz at the vutex c'. By Theorem 5.1, the maxim genus of the subgraph
G' consisting of R3 at c, R2 at c', and the path of bridges fro: c to
c' is given by the formula YH(G') - YH(R3) + Yumz) - 2. Thus, we
know YH(G) Z 2, which is a contradiction. This completes the proof.

is have considued what could happen in a graph of maidens genus
one if one cutpoint of the graph has nontrivial multiplicity three.

He now considu what might happen if thus is no such vertex.

M. Let c be a connected graph with m(c) - 1. Suppose that
G has no cutpoint of nontrivial multiplicity three. Then G has no more
than two cutpoints of multiplicity two. Furthumore, thus are exactly
two such cutpoints only if they share a nontrivial block, and this block
is eithu a cycle or a block of maximum genus one.

1329;: He first show that if thus are two cutpoints of nontrivial
multiplicity two, they must share a nontrivial block. After: having

55
shown this, we will show that there are no more than two such cutpoints.
This rather inverse order of proof is required because the first given
is needed in proving the second.

Let two cutpoints of nontrivial nultiplicity two or more be c and
c'. Then G contains snbgraphs R2 and B5 with centers at c and c' respec-
tively. There is a path in G from c to c'. Let G' be the subgraph
of G composed of Ra, R5, and this path. Then, again by Theorem 5.1,
“(6') - “(112) + “(35) - 2, which, since 0' is a subgralm of c, is
a contradiction. Hence, if two such cutpoints exist, they lust share
a nontrivial block.

Now suppose that G has three or more cutpoints of nontrivial lul-
tiplicity two. By the above argunent, there must be one, say c', which
shares a nontrivial block with each of the two other cutpoints. Hence,
we have four blocks appearing in a ”chain”, each sharing a vertex with
the next. An illustration of the nanner in which the blocks nust be

distributed follows .

 

For blocks G2 and G , there are two cutpoints involved in the ”chain"
arrangement. Choose a cycle in each block which contains both of these
vertices. Choose a cycle in G1 through o1 and a cycle in G” through on.
Then, we have a subpaph of G which is a chain graph of length four
with base a cycle. By Theora 5.13, this graph is upper imbeddable and
consequently has maxim genus two. This is the desired contradiction

of the maxim genus of G. The leans is proven.

56
we are now ready to suanarize these lemmas and to give a theorem

which is a characterization of connected graphs of maximun genus one.

Theorea 5.18: Any connected graph with maximum genus one is a graph
of the kind described in Corollary 5.2. Furtheraore, exactly one of

the graphs G1, described in that corollary, is not a cycle or K This

2.
exceptional graph is either a rose graph with two petals, a rose graph
with three petals, a non-block chain graph of length three with a
cycle as its base, or is a block of naximua genus one.

Proof: If a connected graph were not one of these kinds, one or
more of Lemmas 5.13-5.17 would be contradicted.

Since the graphs described in Theorem 5.18 are of maximum genus
one, that theorem is a necessary and sufficient condition for a graph
to have maximum genus one.

we close this chapter with a brief discussion of blocks of sax-
inua genus one.

As was mentioned earlier, any block with naximun genus one is
necessarily planar. Theorem 5.11 indicates that a block of this type
lust contain a subgraph homeomorphic to either H or Q, as described
in that theorem.

To determine the "kinds" of blocks which might have aaximum genus
one, one would only need to begin with H or Q (or a subdivision of one
of them) and add vertices and edges subject to two conditions. First
the graph obtained must be a planar block. Secondly, its aaxisun genus
must be exactly one.

The problen of detersining whether a given block has maximum genus

one is made easier by using the above processes. At each new addition

57

of vertices or edges, one looks for butterfly, rose, or chain subgraphs.
If one obtains a rose with four petals, a butterfly with four wings, or
a chain graph of length four, he has added vertices and.edges in an
improper manner. Any of the graphs Just listed has maximum genus two.

The theorems in this chapter are all the equipment which is neces-
sary to examine blocks of maximum genus one. Figure 5.4 shows the man-
ner in which a block of maximum genus one is obtained from a butterfly
B2, and also shows a graph which is obtained which does not have max-

imum genus one.

 

\\
\
/
E32 7’ 1 -—’

.’ >

Figure 5.# Obtaining a Block of Maximum Genus One.

'Y =.?

H

cams-36
mmmmmm

He now turn our attention to the examination of graphs which have
the property of being upper imbeddable. However, it is also convenient
to consider simultaneously those graphs for which their ordinary genus
attains a certain lower bound. He will call such graphs lower imbed-
dable.

We first discuss a conjecture made by Duke. is show that his con-
jecture is true for all graphs which are lower imbeddable.

Our next consideration is to discuss graphs of each of the two
kinds, and then we will display examples of graphs with various combin-
ations of these two properties.

We then devote some attention to the problu of determining when
a connected graph is upper imbeddable, given that some or all of its
blocks are upper imbeddable. He conclude the chapter by building an
infinite chain of upper imbeddable graphs. A subclass of these graphs,
called the equilateral triangle graphs, are then upper imbeddable.

He reiterate that a graph is m im&ble if its maximum genus
is the upper bound of possible genera, namely [418(6)].

To simplify the notation throughout this section, we define two
new parameters for a connected graph G, which we designate as 110:)"
and 12(G).

58

59
15(6) - 13/6 - w - 2)
15(6) - E/h - W - 2)

If the connected graph K2 is excluded from consideration, Beineke
and Harary [6] have shown the following inequalities:

y(c) 2 81(6)} if c is any connected graph,
v(G) _>_ {12(G)3 if G is a connected graph without triangles.

Because of these inequalities, it some appropriate to make the
following definition.
Aconnected grathof orderpZBwillbecalledlmW
i.) if c has triangles and y(c) - {15(6)} when x1(c) > 0 or
y(c) - 0 when x1(c) 5 0.
ii.) if c has no triangles and v(G) - {12(6)} when x2(c) > 0 or
y(c) - 0 when 12(0). _<_ o.

The above definition consists of two parts because the inequality
given by Beineke and Harary has two parts. The definition is made so
that those graphs which have no triangles may also be lower imbeddable.
Had the definition not been made in this manner, a graph without tri-
angles could be lowar imbeddable only in those cases where {11(93 '-
{15(6)}.

The definitions imply that any plamr graph is lower imbeddable.
We also remark that KP, p Z 3,and Km,n are lower imbeddable graphs.

The following mark clarifies the definition.

Remark 6.1: Let c be a connected graph without triangles. If x1(c) > o,

s... {15(6)} 412(08-

60

2133;: It is obvious that §x2(c)3 _>_ {x1591 for all connected
graphs. The proof need only show that equality cannot hold if 5(a) > 0.

Since x2(c) - 11(6) - {2, then if fxfic)‘; - {x593 , clearly
E < 12 since xz(c) - x1(c) < 1. Because 11(6) > 0, then v < 6.

The connected graphs without triangles having fewer than six ver-
tices may be observed to have x1 less than or equal to zero.

Hence, there are no graphs without triangles for which {11(6)} -
{5(a)} and for which 5(a) > o.

In the last chapter we noticed the applicability of the edge adding
technique in finding the maximum genus of upper imbeddable graphs.
These successes might cause us to turn to the same technique to estab-
lish the ordinary genus of lower imbeddable paphs. However, the number
of orbits in the minimal imbedding of a lower imbeddable graph is not
as easily handled as was the nuaber of orbits in a maximum imbedding
of an upper imbeddable graph. The following remark formalises this fact.

w: Let G be a connected lower imbeddable graph with I: edges,

and let 1"“ be the number of faces in a minimal imbedding of G. Then

i.) {3% - 2g 5 F” 5 [3%] if c has triangles, and
ii.) {pa - 35 r“ 5 [em] if c has no triangles.

Proof: This result is a simple application of Euler's formula,

obtained by placing either blank or {12(6)} for the genus.

As one can see from this remark, to "build" one lower imbeddable
graph from another apparently demands different methods than those used

61
for upper imbeddable graphs. As of this time, the author has been

unable to apply a technique successfully to such graphs.

is would next like to discuss a conjecture made by Duke [it] . He
conjectured that the Betti number and the genus of am graph are related
by the inequality 8(6) 2 #70:). He will show that this conjecture is
true for planar and toroidal graphs and for all connected graphs which

are lower imbeddable.

mm 6.3: If G is a connected toroidal graph or if G is any connected
lower imbeddable graph, then 8(a) a m(c).

M: If G is a planar graph, then hy(G) - O. For any connected
graph we havesgv - 1, thus ago-Mm).

Suppose y(c) - 1, then it follows from Kuratowski's Theorem that
m(c) a 2. Now, 8(6) 2 2 m(c) a 1;. Hence, 3(6) 2 uy(c) for toroidal
graphe-

Now assume y(G) a 2 and c is lower imbeddable. Since vac?) - 1,

then V Z 8 for all graphs being considered. Hence, E + 3V 2 31 for all

such gaphs.

9591;: Suppose G has triangles. f

Thus, Y(G) - {11(6)}. Then 7(a) < x1(c) + 1. So, lw(G) < 2% - 2v + 8
andz-g-ZV+8_<_B(G)-E-V+lifandonlyiffl+3V?_21. Gasel
is proven.

M: Suppose G has no triangles.

Thus, y(c) - {5(a)} . Hence. y(c) < 12(6) + 1 - tn - gv + 2. '
3o,tw(c) <E-2V+8andE-2V+8.<.B(G)-E-V+lifandonly
if v ,>_7.

This completes the theorem.

62

Those graphs which we have just considered are of a very special
kind. It seems appropriate to discuss graphs with regard to comparison
of genus and maxim genus. Any connected graph belongs to eractly
one of the following sets:

(1.) Graphs which are both upper and lower imbeddable.

(2.) Graphs which are upper, but NOT lower imbeddable.

(3.) Graphs which are lower, but NOT upper imbeddable.

(1h) Graphs which are neither upper nor lower imbeddable.

Theorem 6.1“ hch of the sets of graphs described above are nonapty
sets of connected graphs. Furthermore, each set contains graphs where
the appropriate parameter X1, 1 -1, or 2, is positive as well as non-
positive.

m: To prove the theorem we need to display at least one graph
with 11, i - l or 2, negative or zero and one with the parameter posi-
tive in each of the four sets.

Sgt ‘1.) Upper and Lower Imbeddable Graphs

Throughout this thesis we discovered more examples in this set than
any of the other three. By the work in other chapters of this thesis,
the complete graph, the complete bipartite graph, the wheel graphs, and
the standard maximal planar graphs, are all examples of graphs {in this
set.

Set .) Upper, but not Lower Imbeddable Graphs

a.) we first display a graph which has no triangles and has
X2(P) < o.

The Petersen graph P was shown to have maximum genus three in

Remark 2.1. It is well known that the genus of this graph is one.

63
However, 1:203) - 15/1; - 8/2 < 0. Thus, to be lower imbeddable, it would
have to be a planar graph. Hence, P is not lower imbeddable. Further-
more, 8(P) - 15 - 10 + l - 6. Thus, P is upper imbeddable.
b.) we now display a graph which has triangles for which 11(6) > 0.
Let G be the following gaphc

0 LG .

The following parameters are those of G, where we make use of the well

 

known theorem concerning the genus of a graph and the genera of its

components. We also use Theorem 5.1 of Chapter 5. The parameters are:

no) - mm) + mm) + o - a > e - {5(a)}.
m(c) - yuan) + Yu‘fio) + o - 36 -[ia(c)] .

Hence, G is a graph which is contained in Set (2.).

Set (3.) Graphs which are Lower, but not Upper Imbeddable

Let G be any, cactus with disjoint cycles, numbering at least three.
Then the Betti number of G is at least three, but G is a planar graph
withmaximumgenus zeroes shownin'lheor- 5.11. ThasGis notupper
imbeddable. However, because every planar graph is lower imbeddable,
c is a lower imbeddable graph. The parameter x1(c), i - l or 2, is
nonpositive for this example.

We new display an example of a graph G with 5(3) 3' 9. Let G be

the following mph 3

<9 0

 

6‘}

Then 11(G) - 7/6 and thus {flung - 2. However, it is clear that the
genus of G is given by Y(G) - y(K7) +-Y(K7) - 2. Hence, G is lower
imbeddable.

The Betti number of c is 30, and thus 113(6) - 15. However, by
Theorem 5.1, Ya“) - yum?) + yu(x7) - la. Thus 6 is not upper imbed-
dable.

Sgt (h.) Graphs which are neither Lower nor Upper Imbeddahle.

a.) x1(c) < 0.

Let G be the following graph:

@ AA.

Then the Betti number of G is eight, but its maximum genus is three.

 

Although X1(G) - ~3/2, the genus of G is one. G is in Set (4t).
b.) x1(c) > 0.
Let G be the following graph:

”A A A.

Then the Betti nusber of G is 30, while the maximum genus is Lb. Hence,
a is not upper imbeddable. We have x1(c) - 5/6, while the genus of c
is 3. Thus G is not lower imbeddable. G is a graph in Set (h.).

By generalizing the examples in Sets (2.) and.(h.), it is clear-
that each of the four sets is infinite. This completes the theorem.

65

Theorem 6.1% indicates that there is no dependence between the con-
cepts of upper and lower imbeddability. We have established the conjec.
ture of Duke for all planar and toroidal graphs and for all graphs
which are in either Set (1.) or (3.) above. If there does indeed exist
an exasple proving the conjecture to be false, a likely place for it
to appear would be in Set (lb) of the last theoru. It is in this set
that the difference between the maximum and ordinary genus is most likely
to be less than the conjecture allows. ‘

Throughout the remainder of the chapter, we devote our attention
to upper imbeddable graphs. We begin with a theorem which is in reality
a corollary to Theorem 5.6. We use the theorem to establish some results
concerning graphs with certain upper imbeddable blocks. He first intro-
duce some necessary notation. Let G be a connected graph and G' be a
subgraph of G which contains a cutpoint c of G. By G - G' we mean the
graph ded'ined by. v(c - c') - v(c) n c(v(c')) U {o} and
2(0 - c') - m(c) n c(a(c'), where 0(5) is the couple-est of the set 3,
s - v(c') or m(c').

w: Let G be a connected graph with a subgraph G' which con-
tains a cutpoint c of G. Suppose that G - G' is also connected. Let
Fbethenumberoffaces inanimbeddingofG' andr'bethenumberof
faces in some imbedding of G - G'. Then thue is an imbedding of G
withF-I-ll" -lfaces.

my Ifn-linTheorem5.6andG1-G', Gz-G-G', the

theorem is an immediate consequence.

66
The above theoru yields the following corollary which is often
helpful in determining whether a graph is upper imbeddable. In order
to facilitate the statuent of the theorem, we sake a definition.
If G is a connected graph which is not a block. an M of
G is a block which contains exactly one cutpoint of G. If G is a block,

G is considered to be its own endblock.

Coral-lg 6.6:, Let G be a connected graph with an endblock H which is

upper inbeddable. Suppose flirther that G - H is also upper imbeddable.

If either H or G - H has even Betti nunber, then G is upper isheddable.
2E9!) Let F and I” be the nuaber of faces in urine inbeddings

of H and G - K, respectively. Then. by meoru 6. 5, we have

53(9) 5 r + r - 1. However, since either H or c - H m even Betti

nunber, :- + 1!" 5 3, and thus 6H(G) _<_ 2, and c is upper inheddahle.

The following corollary was done with a counting argunent by Nord-
haus, Stewart, and white [10] . The proof given is independent of the

earlier proof.

Gorole 6.2: If G is a connected graph with all of its blocks being
upper imbeddable with even Betti nuaber, then G is upper inbeddable
With even Betti number.

m: The proof follows directly fro- Corollary 6.6.

Carola 6.8: Let G be a connected graph which is upper imbeddable.
Then G is contained in an upper iabeddable graph with an arbitrarily
large nunber of blocks , all but one of which are isomorphic.

67
groggy Choose an arbitrary upper imbeddable graph H which has even
Betti number. Construct a graph G' by attaching H at any vertex of G,
the given graph. He then attach another copy of H to H, etc.
We use induction on the number of copies of H and Corollary 6.6
applies to make any such graph upper imbeddable. It obviously satisfies
the isomorphism prOperty stated.

The following is an example of such a graph where the graph H is K a

5

we now consider the more general problem of the relation of the upper
imbeddability of a connected graph given that all of its blocks are upper

imbeddable. We obtain one negative result and state a conjecture.

Remark 6.2: A connected graph all of whose blocks are upper imbeddable
need not be upper imbeddable.
Proof: We simply display an example of a graph whose blocks are

all upper imbeddable and which is not itself upper imbeddable.

A .

we see that m(c) - 1 f 2 - am), by Corollary 5.2.

 

He complete this section of the chapter by stating a conjecture.

Con ecture: If G is a connected graph none of whose blocks is K2 and

each of whose blocks is upper imbeddable, then G is upper ilbeddahde.

68

We conclude chapter 6 with a theoru which presents an infinite
chain of upper imbeddable graphs , with each a subgraph of the one
following it and a supergraph of the one preceding it. We obtain the
mamum genus of the equilateral triangle graphs as a corollary.

Let c be a connected graph and label a path in c of length (n-1)
by l, 2. ..., n. Define the graph Gn as follows (where + means adding
the indicated edges):

n n n
Gn " G + 2 (3.93) + 2 (J:(J+1)') 4' Z (3.:(J+1)')e "ha-‘9
3'1 3'1 3'1
152', ..., (n+1)' are pairwise nonadjacent vertices which are not in G.
(See Figure 6.1).

Theorem 6.10: Let G be a connected graph with an i-face imbedding,

(“NY 2’ I,

 

Figure 6.1 The Graph Gn

i - l or 2, and Gn be as defined above. If i - 2. assume that the vertex
labeled "1" is involved in the two faces of the imbedding. Then Gn has
a (3-i)- face cellular imbedding for each n and is thus upper imbeddable.
Furthermore, if i - 1, then the two face imbedding of on has (-n'-(n+1)'-n-)
as one of its two faces.

m: We begin with the graph G and add nodes and edges in order

to form Gne

69
we first add the nodes 2'.....(n+l)' and the edges (j.(j+l)'),
where J - l,2,...,n. For this new graph Go we also have a cellular
imbedding with i faces.
It is now most easily done by considering two cases. He consider
thecasesi-landi-Z.

Easels.) 1'“ 1 " 1-
He then have an imbedding with one face for 60' He write it

(...-1-2'-1-...-2-3'-2-...-3-(5+1)'-j-...-n-(n+1)'-n-...),

where J - 3,...(n-l). The proof now proceeds by induction on the num-

m m
berm, where we formG -G +2 (j',j) +2 (j',(j+l)': l§m_<_n.)
m 0 3'1 3'1

Let n ' 1e
we add the edge (151) into the face listed above as follows:

<eee'1'2."'1"1.-1eee'J'(J+l)"j'eee)g Uh”. J . 2,...,n.
o 1’ l

Schematically, we represent the face as follows: [Q]: .

l
I

W
("0' K

Because this new graph has a cellular imbedding with only one face, we
may add the edge (1'.2') as is indicated in the following diagram and
have a cellular imbedding of the new graph with two faces. Schematically,

O O |
'1 Z,
I
(“+13 I'
n I o

The faces for this new imbedding are as given at the top of page 70,.

7o
(...-1-2'-1'-l-...-j-(j+1)-j-...), where J - 2,...,n ,
and
(~1'-2'-1-) .
Consequently, the theorem is true if m - 1.

Now let a - 5+1 and suppose G has a two face imbedding where one

.1

of the faces FA is -j'-(j+l)'-j- . Then the edge ((3a), (5+2)') has

both of its corresponding directed edges in the other face lb. Because

the vertex (j+2)' has degree one, the face Eb lust have the following

appearance:

(o-o-(J+1)-(J+2)'-(J+1)-...).

We write the two orbits of the imbedding schematically,

(sci-Y
(.3?!)
. ’ 3
e) .
F 5*.
B

(3+!)’
We now add the edge ((j+l)', (j+2)') and combine the faces in the

following manner:
J" (34:).

 

:) (.3?!)
, \
3
;l§“ I ___> I ’
(591) (St:)
I
(5+2) /

71
So that we now have a one face imbedding of the newly formed graph.
We now proceed exactly as in the case n - 1, adding the edge
((#1)‘, (34-1)), yielding a cellular imbedding of the graph for

n - 3+1 with two faces, which are:

(-J'-(J+1)'-J+1)--o-(J+1)-(J+2)'-(J+1)'-J-),
and
(-(5+1)'-(J+2)'-(J+1)-) .

By induction, Case 1 is completed.

G_a_s_e_g_. Let i - 2.

After we have formed 00' we now have a graph which has a cellular
imbedding with two faces. We use induction on m as in Case 1.

Let m . 1. By assumption, the original imbedding of G was so that
the vertex labeled 1 was involved in each of the two faces of the imbed-
ding. This will still be the case for the two face imbedding of 60’

Let FB be the face of the imbedding which contains the directed edges
[l,g'] , [251], which necessarily abut since 2' has degree one.

The vertex “1" must also be involved in another face, which we
call FA' We add the directed edges [1,1'] [151] into this face, again
so that they necessarily abut.

Then since [1m] and [l,l'] are in different faces, the edge adding
technique allows us to add the edge [2',1'] so as to have a cellular
imbedding of the resulting graph with one face. The induction is anchored.

Now let I: - k+l and suppose the graph G1: shown below has a one face

cellular imbedding.

72

 

 

 

we add the edge ((j+1)', (3a)) to ck. By the edge adding tech-
nique, we may add the two corresponding directed edges so that they are
in different faces of the new two face imbedding.

Since the degree of (j-i-l)’ is now at least two and since (J+1)'
is in both faces of the new imbedding, there is some vertex p in V(Gk)
so thatthe directed edge [p,(j+l)'] is in a different face from the
directed edge [(Jfl), (j+2)']. By the edge adding technique we may
add the edge ((3+1)5 (342M so as to form a cellular imbedding with
one face for the newly formed graph.

By induction, the proof is completed. We close with an illustration
of the way in which the edges were added in Case 2.

  

(Ac-I).

 

”on' ‘

G“ 9' (K+I’(kn)')

 

     

WE

(K'l)7-K*')'

GK'I

(_hu)’

73
Corolla 6.11: Let G be an upper imbeddable graph. Then there is a
chain of upper imbeddable graphs,

- C C- Eeee e
c; clg G2C_'.G3_. . . k_.Gk+1

Furthermore, for each i, G - G is a planar graph so that in its planar

i
imbedding all but one of its faces are triangles.

2339;: To form G1+1 from C1 we do exactly as in the theorem if

i - 1; if i f l we use 61 as the graph in the theorem and the path

consisting of the triangles added to G1_1 to form G1 as the path in

the theora. The theorem assures that if 61 has a two face imbedding,
there is a vertex in this path which is involved in each of the two

faces. Hence, the theora constructs the chain of graphs as desired.

99W: We call a graph which is obtained from K3 by n applica-
tions of the building procedure described in the theorem, the W

m graph with :1 layers, and denote it by En. Then In is upper
131)“qu

329;: This is a restatement of the theorem with G - K3.

CHAPTER?

THE HAXIHUH GENUS OF THE (3)!le BIPARTITE GRAPH Km,n

AND THE COHPIEI'E GRAPH Kn

After investigating upper imbeddable graphs in general in Chapter
6, we now turn to two important special graphs of that kind, nanely
the complete graph Kn and the complete bipartite graph Km,n' The
determination of the maximum genus of these graphs is made by an appli-
cation of the edge adding technique. It should be remarked that the
maximum genus of the couplets graph Kn was first determined by Nord-
haus, Stewart, and white [10] . The proof given there is based complete-
1y on almonds ‘ vertex permutation technique, while that given here
is essentially an edge adding technique.

The method of proof is to state and prove a general theorem con-
cerning this edge adding technique and to show its application to the
particular graphs mentioned above. It is rather surprising that the
resulting theoren applies to both classes of graphs. This theorem
deals with adding a single point to the vertex set of an upper imbed-
dable graph. He then add edges from this vertex to each vertex in a

prescribed subset of the vertices of the original graph.

Theorem 2.1: Let G be a connected graph with an i-face cellular imbed-

ding, where i - 1 or 2, so that G is an upper imbeddable graph. Let

S be a nonempty subset of WC), with ‘8] - n. If i - 2, assume that
74

75
8 contains two vertices s and t with s appearing in one face and t
appearing in the other face. Further assume that the degrees d(s)

and d(t) both exceed one. Let S be a subset of S with J elements

3
and let p be a vertex not in the vertex set of G. we assume

3 - an: Sh-13"'331 -fell, .1- l,...,n. we define graphs Gr,
r - l,...,n, as follows (where +£ means adding the indicated edges
to the graph):

G1. - G + 2 (p,s).
seifir

The vertex set of Gr is composed of the vertex p and the vertices of

G. Then, for r»- 1,..., n.

G1. has a cellular imbedding with 1 races for odd r,
G1. has a cellular imbedding with.(3-i) faces for even r,

Egggfx we consider the cases i - l and i - 2.

§§§24l. Let i - 1. Then there is a cellular imbedding of G
with one face on some compact orientable 2-manifold.

Label the vertices of S with the integers l,...,n in a manner so
that Sr - {l,...,r} for r - l,...,n. Since a vertex of degree one may
be added within a face, we add the undirected edge (p,1) so that the
resulting graph G has a «11an imbedding with one face. If |s| - 2,

1

the edge adding technique implies that G has a cellular imbedding with

2
two faces and the theoren is thus proven. Hence, we assume that S
has three or more elements.

we now proceed inductively. Suppose that we have formed G1 and

that G1 has a cellular imbedding with one face. He show that G1+1

76

has a cellular imbedding with two faces and that G1+2 has a cellular

imbedding with one face. Since G1 has an imbedding with only one face,

the edge adding technique implies that the undirected edge (p,i+l) can
be added in only one way. Namely, so that the resulting graph G1+1
has a cellular imbedding with two faces. The technique also describes
a manner in which (p,i+l) may be added so that the directed edges
[p,i+l] and [i+l,p] are in different faces in the resultant imbedding.
He so add the edge (p,i+l).

The imbed-

we now form an imbedding for G from that of G1+

1+2 1'
ding formed will have one face. By the edge adding technique, we can

Obtain such an imbedding for G if we can establish the following

1+2

fact: There is a vertex v in V(G ) and a vertex 3 in S so that

i+l i+l
the directed edges [j,p] andly,i+2] are in different faces of the two

face ilbedding of Gi+1'

We find these vertices by considering all the directed edges of

the form [k,p], k - l,...,i+l. Since the imbedding of G has only

1+1
two faces there are vertices v and j as desired if not all edges of

this form are in the sane face. This is because the vertex 1+2 must

occur in some face of the imbedding. we choose some R0 in V(Gi+l)

so that [k0,p] is in a face different from the one chosen for 1+2.
Then ko - J above and any adjacency of 1+2 with its edge directed into
i+2 in the chosen face could serve as v above.

Recall that the edge adding technique was applied to insure that
the directed edges [i+l,p] and [p, 1+1] are in different faces for the

two face imbedding of G Furthermore, p must have degree at least

1+1'

two. Thus, there is some n 6 V(G so that the directed edge [mp]

1+1)
precedes the directed edge [p,i+l] in some face; a.f 1+1 since p has

77
degree at least two. Hence [m,p] and [i+l,p] are in different faces.
Thus, not all edges directed into p are in the same face; as stated
before, we then have the vertices v and j as desired above. we thus
add the edge (i+2,p) so that G1+2 has a cellular imbedding with one
face. He have completed the induction.

Notice that we now have 61’ Gi+1' and G1+2 with cellular imbeddings
of one, two, and one faces respectively. Since we began with G1 having
an imbedding with one face, the number of faces in the imbeddings for
the Gr' r -l,...,n are exactly as described in the theorem. This
completes Case 1.

§§§g_§. Let i a 2. Then there is a cellular imbedding of G with
two faces on some compact orientable 2-manifold.

we begin by using the additional hypothesis we are given when
G has a two face imbedding. Thus, we may assume that there are directed
edges [m,s] and [c,t] which are in different faces of the imbedding.
Call the faces F' and F” respectively. we relabel s with the label
"1" and t with the label ”2".

we add the edge (p,l) so that the directed edges [l,p] and[p,l]
are both in the face F'. We have then formed G1 and have established
a cellular imbedding of it with two faces. By the edge adding technique,
we may add the edge (p,2) so that G2 has a cellular imbedding with one
face. (we choose the face F“ at the vertex 2 and are assured that it
is different from F'. The edge adding technique can then be applied
so that we obtain an imbedding with one less face.)

To complete the proof of the theorem, one need only substitute G2

for G in the argument for Case 1. Since, however, we began with G

1 l

78
having an imbedding with two faces, the imbeddings have the number of
faces described in the theorem.

This completes the proof of the theorem.

It is clear that the above theorem is designed to give us a method
of building upper imbeddable graphs from a given upper imbeddable graph.

It has the following corollary, analogous to Corollary 6.11.

Carol .2: Let G be an upper imbeddable graph. Then there is

a chain of upper imbeddable graphs GlC 02C... so that

Mai)! - |v(ci_l)| - 1.

The purpose of Theorem 7.1 is to aid in the induction argument
for the determination of the maximum genus of both the complete graph

and the complete bipartite graph. He now undertake this task.

Theorem 2.3: The complete graph Kn on n vertices is an upper imbed-
dable graph, and
mac”) - [t(n-1)(n-2)].

113331;; We use mathematical induction on the number of vertices :1.

Let n - 1. Then 80(1) - 0; thus since YH(K1) $[%B(K1)] , we have
YM(K1) - 0. The case n - l is completed.

He now notice that we have our induction anchored at a number which
is congruent to one modulo four. We proceed inductively.

Let in 1(mod 4) and assume the induction twpothesis that K1 has a
one face cellular imbedding. Vs show that each of the four graphs K

1+1’

K 1+“ is upper imbeddable. We do so by showing that the

i+2’ Kit-3’ K
four graphs have cellular imbeddings of one, two, two, and one face

respectively. Before going further with the actual arguments, we show

79

that we are indeed looking for cellular imbeddings with the listed
number of faces. Recall that a graph with even Betti number is upper
imbeddable if and only if it has a cellular imbedding with one face.
Similarly, one with odd Betti number is upper imbeddable if and only
if it has a cellular imbedding with two faces. we examine the parity
of the Betti numbers of the four graphs listed above. We first note
that for any complete graph KP, B(KP) - %(p-l)(p-2). For the graphs

in question we have the following Betti.numbers and their paritiesx

5(K1 +1) - %(i-l)i, which is even since i-l is divisible by four.
B(K1+2) - %(i+l)i, which is odd since both i and %_-(i+l) are odd.
B(K1+3) - -§-(i+2)(i+l), which is odd because both 1+2 and 12~(i+1) are odd.

80:1”) - §(i+3)(i+2), which is even since i+3 is divisible by a.

Hence, the imbeddings must have the number of faces listed above. We
now proceed with the proof.

The proof consists of repeated applications of Theorem 7.1. At
each step we will indicate which set we adopt for S and which of the
Cr in the theorem is the desired new graph.

1 from K1 we let S - G - K1 and label the vertex to

be added with the label 1+1. Since K1 meets the hypothesis of the

theorem, the conclusion applies. Hence the graph G1 has a cellular

Tb form K1+

imbedding with one face, since i is odd and since K has a cellular

1

imbedding with one face. It is clear that K - 61' and the case K

1+1 1+1

is complete.

Fer the case K , we let S - K and label the new vertex i+2.

1+2 1+1

Then K1+2 - G1+1 in the theorem. Since 1+1 is even, the theorem implies

80

that K has a cellular imbedding with (3-1) - 2 faces. K is as

1+2 1+2

desired.

Fbr K1+3, we let S - K1+2. Since K1+2 has an imbedding with two
faces, there must be two vertices which are in different faces. In
the notation of the theorem G1+2 - Ki+3'
has a cellular imbedding with two faces, as desired.

Since i+2 is odd, the theorem
implies that K1+3

Tb complete the induction, we need only display an imbedding of
K1+u which has one face. The procedure is the same, letting S - K1+3.
Then K1+4 - G1+3. Since i+3 is even, Ki+4 has a cellular imbedding
with (3 - 2) - 1 face.

This completes the theorem.

Before proceeding to the next theorem, which establishes the max-
imum genus of the complete bipartite graph, we make the following remarks
concerning the Betti number of such a graph.

The Betti number of the complete bipartite graph K.'n is given
by the formula B<Km,n) - (n-l)(m-l), which is odd only if both m and n
are even. Hence, in the proof of the theorem which follows we will
be looking for a cellular imbedding in which the number of faces is
one in all cases except where both m and n are even. In this excep-
tional case, we need to find a cellular imbedding with exactly two

faces.

Theorem z.#: The complete bipartite graph K. n is upper imbeddable
D .
for all m and n. The maximum genus is given by the formula:

yum“) - [%(n-1)(--1)].

81
Proof of Theorem .4 He prove the theorem by fixing n and using

induction on m. The Betti number of the graph K n is zero, thus by

1:
the upper bound theorem we must havs‘YH(K1 n) - O, and the theorem is
3

true for m - 1.
Assume as our induction hypothesis that the graph Ki,n is upper

imbeddable. is show that K n is upper imbeddable.

1+1,
As one might suppose, our method is to apply Theorem 7.1 to the

imbedding of K1 n and get the desired imbedding for K The proof
2

i+l,n'
is done in two cases depending on the parity of n.

Case 1. Let n be odd.

By the remarks preceding this theorem, the Betti number of K1 n
D

is even, and thus K n has a cellular imbedding with one face regard-

1.

less of the parity of i. In Theorem 7.1, we let a - K and s - fig,

i,n
the part of K1 n with n vertices. In the notation of Theorem 7.1, we
0

have Gn - Ki+l,n'

which agrees with that of K

Hence, since n is odd, Gn has a cellular imbedding

i,n in its number of faces. Thus K

has a cellular imbedding with one face. Since K

i+l,n

i+l,n has even Betti

number, this is exactly what we desired.
Case 2. Let n be even.

The number of orbits in the maximum imbedding of K now depends

i,n

on the parity of 1. He consider the two subcasesx
Case a. Let i be odd.

we then know that K1 n has a cellular imbedding with one
0

i+l,n from K1,n °X30t1y as was done in Case 1.

However, since n is now even Gn.has a cellular imbedding with

face. He form X

3-1 - 2 faces. Thus, K has a cellular imbedding with two

i+l,n

Since 8(x ) is odd, this is as desired.

i+l,n

82

Case b. Let i be even

In this case we know that i Z_2 and that K n has a cellular

1.
imbedding with two faces. Consequently, before we can apply
Theorem 7.1 we must find 3 and t in in as described in that theorem.
Since i.Z_2, and since we may assume n 2;2 by using an argument
analogous to that for the case m - 1, any face in an imbedding of
Ki,n must involve at least two vertices of Hg, as the illustration
'mg5‘fit shows. So, let 3 be any vertex of H;. we add
the undirected edge (i+l,s) inside a face of the imbedding for
Kim. Then the directed edges [1+1,s] and [s,i+1] are both in the

same face F. However, since K has two faces in this imbedding,

i,n
there must be a vertex of K; which appears in some other face F'.
we label this vertex t. The vertices s and t are then as desired
in Theorem 7.1, with s - in.

In the notation of Theorem 7.1, we have C - K Since

n i+l,n'
n is even, Ch has an imbedding with 3-2 - 1 face. Because 1+1
and n are both odd, this is as desired.
Case 2 is now completed. By induction the graph Km,n is upper
imbeddable for all m and n, since we could now repeat the above argu-

ments with m fixed.

The theorem of Duke [h] given in Chapter 3 which concerns the deter-
mination of those compact orientable 2-manifolds upon which a given
graph has a cellular imbedding, can now be applied to give the follow-
ing corollaries.

Coro . z The complete graph Kn has a cellular imbedding on an

orientable surface Sk of genus k if and only if:

83.

Lnfiggn-fl} S k 5 [%(n-l)(n-2)] .

 

Corollggy 2.2: The complete bipartite graph Km n has a cellular imbed-
D

ding on an orientable surface Sk of genus k if and only if:

{s(n-2)(n-2)k 5 s s [hens-1)].

BIBLIOGRAPHY

9.

10.

ll.

12.

13.

11+.

15.

16.

BIBLIOGRAPHY

J. Battle, F. Harary, Y. Kodama, and J. U. T. Youngs. Additivit
of the Genus of a Graph. Bull. Amer. Math. Soc. 68 (1962,, 565-568.

M. Behzad and G. Chartrand. An Inproduction to the ‘Iheog of
Graphs. (to appear)

J. Dugundji. Topology. Allyn and Bacon, Boston (1965).

R. Duke. The Genus. Regional Number. and Betti Nunber of 8. Graph.
can. Jo Hath. E 19 ’ 817’822.

J. Ednonds. A Conbinatorial Re resentation for Pol hedral Surfaces.
Notices Amer. Math. Soc. 1 (196(2),, 6R.

1". Harary. Graph meog. Addison-Wesley, Reading (1969).

G. Kuratovski. Sur la Problene des Gourbes Gauchos on To 01 ie.
Fund. Math. 1.; (1930;, 271-283.

I. S. Massey. figebraic Topolpgn an Introduction. Harcourt,
Brace, and world 19 7 .

E. Nordhaus, R. Ringeisen, B. Stewart, and A. White. A Kuratmlski-
me Theorem on the Genus of 8. Graph. (to appear).

E. Nordhaus, B. Stewart, and A. White. On the Maximum Genus of a
Graph. (to appear in J. Conb. m.)

 

o. Ore. 'Iheog of Graphs. Amer. Math. Soc. (1967).

G. Ringel. Ihs Geschlecht des Vollstflnd en Paaren Gra hen. Abh.
Math. Sen. Univ. Hamburg pp (19655, 139-150.

G. Ringel and J. H. T. Youngs. Solution of the Heawood Ma Color
Problen. Nat. Acad. Sci. 6_Q (19685, #3835.

U. Vollnerhaus. ”fiber die Einbettung von Graphen in Zweidinensionale

Orientierbare Mannigfaltigkeiten Kleinsten Geschlechts.” in m
Zur Grapbentheorie. Teubner, Leipzig (1968), 163-167.

J. U. T. Youngs. Minimal Inbedd s and the Genus of a Gra h.

J. Math. Mech. 12_ (1963,, 303-315.

A. White. Ihe Genus of Cartesian Products of Gra hs. Ph.D. Thesis,
Michigan State University (1969;.

Ah

  
    

MIC R

\Iiifimififijlfliflilju[l,fiflfljigfiflifmfiflmvVs