, H '. _ .~. ._ . . ., _,,,.Ar..r...;...”n.A._;--‘:-x,.'. ..;.‘_..,_;__ ‘_._-.. .-
‘ —‘ . ‘ “ ' —,”‘ , 0 7
lul‘ . ._ .u.’ j. .‘ E" - .f —_;_

 

GRAPHS AND THEiR
SUBDIVISIONS

Thesis for the «Degree of Ph. D.
WCHIGAN STATE UNIVERSITY
M. IAMES STEWART
1972

   
     

  

LIBRARY

Michigan State
University

 

This is to certify that the
thesis entitled

Graphs and their Subdivisions

presented by

M. James Stewart

has been accepted towards fulfillment
of the requirements for

El; . 12, degree in Mathematics

XJZM/W

Major professor

 

 

0-7639

 

   
  

 
 

800K NNDERYINB.' ‘

LIBRARY 8mm; R51
SPRINGPORI. MlClllBt-tfli

It. I! J- . kn erILIr.

ABSTRACT

GRAPHS AND THEIR
SUBDIVISIONS

By

M. James Stewart

The concept of a subdivision of a graph is an old concept
which is widely used in various graph-theoretic constructions and
underlies the notion of graph-homeomorphism. A particular type of
subdivision of a graph G, denoted by Sn(G) and referred to as the
nth subdivision graph of G, is obtained by replacing every edge of
G by a path of length n + l. The nth subdivision graph of G is
related to three other graph-valued functions: the nth power G",
the total graph T(G), and the line graph L(G). Although the graphs
G", T(G), and L(G) have received a great deal of attention in the
literature, surprisingly little research has been devoted to the
investigation of Sn(G). The main purpose of this thesis is to add
to the knowledge of subdivisions of graphs and, in particular, to
study the properties of the nth subdivision graph and to obtain a
characterization of it.

The definitions of terms referred to in this thesis are

presented in Chapter l, as well as much of the notation that will

M. James Stewart

be employed throughout. A few well known graph-theoretic results
useful in this thesis are also stated here.

The first section of Chapter 2 traces the development of the
graph-homeomorphism concept from its toplogical origins to the
equivalence classes of the relation "is homeomorphic with," where
particular attention is paid to the canonical representatives of
these classes, the homeomorphically irreducible graphs. In addition
to the multiple characterization of these homeomorphically irreducible
graphs in terms of paths, triangles, and matrices, in sections 2.2
and 2.3 several graph-theoretic properties, including colorability,
traversibility, and automorphism groups, and the way these relate to
homeomorphically irreducible graphs, are discussed. In section 2.4
the hamiltonian index of graphs contained in certain homeomorphism
classes of nonhamiltonian graphs is investigated.

A complete characterization of the nth subdivision graph
involving lengths of trails is presented in the first section of
Chapter 3, followed by some considerations of the structural rela-
tionship of a graph G with its nth subdivision graph Sn(G)‘ Except
for section 3.4, which deals with the enumeration of trees having
a l-factor, the remainder of this chapter is devoted to the develop-
ment of various salient characteristics of nth subdivision graphs.
In particular, for any graph G, necessary and sufficient conditions
for the existence of a l-factor of Sn(G), Gn (n 3_2), and T(G) are
obtained in section 3.3 and generalizations of these results
utilizing the edge independence number are discussed in the final

section 3.5

GRAPHS AND THEIR
SUBDIVISIONS

By

M. James Stewart

A THESIS

Submitted to
Michigan State University
in partial fulfillment of the requirements
for the degree of

DOCTOR OF PHILOSOPHY

Department of Mathematics

1972

O9 DEDICATION
1 (9

a“
To
Gary,
Shashi,

Tricia's Mother,

and the Local Leo.

ii

ACKNOWLEDGMENTS

Words cannot suffice to thank my good friends Gary Chartrand
and Shashi Kapoor, who are in large part responsible for giving me
the motivation to initiate research of my own in graph theory.

A special debt of gratitude is owed to my “academic father,"
Professor E. A. Nordhaus, without whose inspiration, guidance, and
psychological support this thesis could not exist. I thank him for
his concern, his knowledge, and the time and effort he has cheerfully
spent on my behalf.

My gratitude goes also to Professors E. M. Palmer and B. M.
Stewart for the helpful suggestions and numerous kindnesses, often
unsolicited, they have extended to me. I thank also Professors
M. Fuchs and V. P. Sreedharan for serving on my advisory committee.

Most importantly, my family has been an unseen but indis-
pensable source of strength to me, especially Joyce 1. Stewart. I
realize better in retrospect than I did at the time just how much
her consideration, understanding, and support has contributed to the
accomplishment this dissertation represents. I am very grateful.

Over and above all else, I thank my wife, Mary-~without her
there would be no point to this endeavor.

Finally, I am indebted to the people of the Lansing Com-

munity College district for their financial support through a

sabbatical leave, and to the Department of Mathematics at Michigan
State University for the gracious hospitality I enjoyed throughout

the sabbatical year.

iv

LIST OF FIGURES ....................
CHAPTER I ............................

CHAPTER 2 ............................

Section 1.1:
Section l.2:
Section 2.
Section 2.
Section 2.
Section 2.
Section 3.
Section 3.2:
Section 3.3:
Section 3.4:
Section 3.5:
BIBLIOGRAPHY

th—l

TABLE OF CONTENTS

Homeomorphic Graphs ...........
Homeomorphically Irreducible Graphs . . .

Some Properties of Irreducible Graphs
Certain Homeomorphism Classes and the

, Hamiltonian Index ............

CHAPTER 3 ............................

The Nth Subdivision Graph and Its

Structure ................
Properties of Nth Subdivision Graphs . . .
Factorization in Sn(G) ..........

The Enumeration of Trees Having a

l-Factor .................
The Edge Independence Number for Sn(G) . . . .

Page

vi

3O
47

57
59

LIST OF FIGURES

Figure Page
2.1 Geometric l-complexes .................. 8
2.2 Homeomorphic graphs ................... 10
2.3 An example illustrating Corollary 2.4 .......... 19
2.4 Homeomorphs H1 and H2 of an irreducible graph

G having |F(H])| < |F(G)| < |P(H2)| ........... 2l
2.5 H is randomly hamiltonian from v, but possesses

a subdivision G which is not hamiltonian ........ 24
3.1 A multigraph M together with S(M) and 52(M) ....... 30
3.2 An outerplanar graph K4-x and its nonouterplanar

subdivision graph .................... 42
3.3 Graphs G such that S(G) has no l-factor ......... 52
3.4 The 10 nonisomorphic rooted trees of order 6

or less having a l-factor ................ 57
3.5 A (6,7)-graph G along with S(G) and 53(6) ........ 63

vi

CHAPTER 1

Section l.l
Introduction

One of the most celebrated theorems in graph theory is
Kuratowski's theorem, which characterizes planar graphs as those
graphs containing no subgraph isomorphic to a subdivision of the
complete graph K5 or to the complete bipartite graph K(3,3). In
addition to its central role in Kuratowski's theorem and in numerous
other graph-theoretic constructions, the concept of the subdivision
of a graph underlies the notion of graph-homeomorphism. This rela-
tion is defined more precisely in Chapter 2 and there is shown to be
an equivalence relation on the set of all graphs.

A graph S(G), referred to as the subdivision graph of G, is
also studied and is an example of a graph-valued function which is
intimately related to a well known trio of graph-valued functions:
the total graph T(G), the line graph L(G), and the nth power G". In
l965, M. Behzad showed that the total graph T(G) of a graph G is
isomorphic to the square of the subdivision graph S(G). The total
graph T(G) of any graph G contains both S(G) and the line graph L(G)
as subgraphs. The nth subdivision graph Sn(G), a generalization of
S(G), is a graph-valued function which is associated with a graph G

and is obtained by replacing every edge of G by a path of length n +l.

Although the line graph, total graph, and, to a lesser extent, the nth
power of a graph have received much attention in the literature,
surprisingly little research has been devoted to the investigation of
the nth subdivision graph function. One of the main purposes of this
thesis is to study the properties of the nth subdivision graph

Sn(G) of a graph G from the viewpoint that the pair [G, Sn(G)] is a
specific instance of homeomorphic graphs.

Definitions of terms used in this thesis are presented in
Chapter l, along with much of the notation that will be employed. A
few well known results are also stated here.

The first section of Chapter 2 traces the development of the
graph-homeomorphism concept from its topological origins to the
equivalence classes of the relation "is homeomorphic with," where
particular attention is paid to the canonical representatives of
these classes, the homeomorphically irreducible graphs. In addition
to the multiple characterization of these homeomorphically irreducible
graphs in terms of paths, triangles, and matrices, in sections 2.2
and 2.3 several graph-theoretic properties, including colorability,
traversibility, and automorphism groups, and the way these relate to
homeomorphically irreducible graphs,are discussed. In section 2.4
the hamiltonian index of those graphs in certain homeomorphism
classes of nonhamiltonian graphs is investigated.

A complete characterization of the nth subdivision graph
involving lengths of trails is presented in the first section of

Chapter 3, followed by some considerations of the structural

relationship of a graph G with its nth subdivision graph Sn(G).
Except for section 3.4, which deals with the enumeration of trees
having a l-factor, the remainder of this chapter is devoted to the
development of various salient characteristics of nth subdivision
graphs. In particular, for any graph G, necessary and sufficient
conditions for the existence of a l-factor of Sn(G), Gn (n 3_2), and
T(G) are obtained in section 3.3 and generalizations of these results
utilizing the edge independence number are discussed in the final
section 3.4.

Section 1.2
Basic Terminology

We set forth here some basic definitions and notation which
will be used in the following chapters. For those terms not given
here, the reader is directed to [2] or [9].

A graph_G is a finite, nonempty set V together with a set E
of two-element subsets of V. Each element of V is referred to as a
ygrtgx_or a point and V itself as the vertex set or point set of G;
the members of the edge set E are called edges, In general, the
vertex set and edge set of a graph G will be denoted by V(G) and
E(G), respectively.

There are variations of graphs to which we shall occasionally

make reference. In a multigraph, we allow the presence of more than

 

one edge joining a pair of distinct points; such edges are called
multiple edges. If loops are also permitted, that is, edges which

join a point to itself, we have a pseudograph.

 

The order of a graph G, denoted [G], is the number of elements
in V(G); if |G| = p and E(G) has q elements, we say G is a (p,q)-graph.
A graph G is called gmpty_if E(G) is the empty set. The gggggg_of a
point v of G is the number of edges of G incident with v and is denoted
degGv, or simply deg v, if no confusion is likely to result by leaving
the graph G unspecified. A point of degree l is called an endpoint
of G. When every point of G has degree r, we say that G is regular
of degree r, or r-regular. Two graphs G1 and G2 are called isomorphic,

 

 

expressed by writing G1 = Gz, if there exists a one-to-one correspon-
dence between V(G1) and V(Gz) which preserves adjacency and nonadjacency.
The subgraph induced by a set U of points of G, denoted <U>,
is that subgraph having U as its point set and whose edge set consists
of all edges of G incident with two points of U. In a completely
analogous way, we speak of the subgraph <F> induced by a nonempty
subset of E(G). If v is a point of G, then G-v denotes the graph
<V(G) - {v}> and, in general, if S is a proper subset of V(G), then
G-S represents the graph <V(G) - S>. Similarly, G-F represents
<E(G) - F> for any proper subset F of E(G), and, in particular, G-x
represents <G - {x}> for any edge x of G. A subset N of V(G) is

independent if <W> is empty. Two graphs are said to be disjoint if

 

their vertex sets are disjoint. The ggjgg_of two graphs G1 and G2

is the graph G given by V(G) = V(G])\S}V(Gz) and E(G) = E(G])K,)E(GZ).
-—For-points u and v of a graph G, a u-v trail is a finite

alternating sequence of points and edges of G, in which no edge is

repeated, beginning with u and ending with v, such that every edge

is immediately preceded and succeeded by the two points with which it
is incident (if we allow an edge to be repeated, we have a pplk_from
u to v). A u-v path P is a u-v trail in which no point is repeated
and the points of P distinct from u and v are called interior points

of P. Two u-v paths in a graph G are vertex-disjoint (or simply

 

disjoint) if they have no vertices in common, other than u and v.

Edge-disjoint paths have no common edge. We say a u-v trail is

 

glp§2g_or pp§p_depending on whether u = v or u f v, and a trivial
trgjl_is one containing no edges. A nontrivial closed trail of G in
which no points are repeated (except the first and last) is called

a gyglg_of G. The number of edges in a u-v trail is called its lgpgtp,
denoted as d(u,v), and a cycle of length n is an n-cycle. A graph

of order n which is a path or a cycle is denoted by Pn or Cn, respec-
tively.

A graph G is connected if there exists a u-v path in G for
every two points u and v of G. The relation "is connected to" is an
equivalence relation on the vertex set of a graph G and the sub-
graphs induced by the points in an equivalence class are called the
components of G. The distance d(u,v) between points u and v of a
connected graph is the length of the shortest u-v path. A point v
of G is a cutpoint of G if G-v has more components than does G. A
plgngOf a graph G is a maximal nontrivial connected subgraph of G
containing no cutpoint of itself. For a connected graph G with at
least three points, the following are equivalent (see Chapter 3):

(l) G is a block.,

(2) Every two points of G lie on a common cycle.
(3) For every three distinct points of G, there is a path
joining any two of them which does not contain the third.

A block of order 3 or more is called a cyclic block while the block

 

of order 2 is called the acyclic block. An endblock of a connected

 

graph G having more than one block is a block containing exactly one
cutpoint of G.
There are several special classes of graphs to which we will

frequently make reference. An acyclic graph or forest is a graph with

 

no cycles. A planar graph is one which can be embedded in the plane.

 

A (planar) graph which can be embedded in the plane such that each of

its points lies in the boundary of the exterior region is called.

 

 

outerplanar. The complete graph Kp has every pair of its p points
adjacent. A triangle is a subgraph isomorphic to K3. A bipartite
graph G is a graph whose vertex set V(G) can be partitioned into two
disjoint subsets V1 and V2 such that every edge of G is of the form
v1v2 where viEE Vi, i = l, 2. If V] and V2 have m and n points and
G has mn edges, we Say that G is a complete bipartite graph and write
G = K(m,n). G. Chartrand and F. Harary ([9], p. 107) have shown that
a graph is outerplanar if and only if it has no subgraph homeomorphic
with K4 or K(2,3), except K4-x (where x is any edge of K4).

To any given nonempty graph G, there are associated with G
several special graphs which we will encounter. The nth power Gn
of G is that graph with V(Gn) = V(G) such that an edge uv €5E(Gn)
if and only if,l §_d(u,v) §_n in G. The line graph L(G) of G has

 

vertex set V(L(G)) which can be placed in one-to-one correspondence
with E(G) in such a way that two points of L(G) are adjacent if and

only if the corresponding edges of G are adjacent. The total graph

 

T(G) has vertex set V(T(G)) which can be placed in one-to-one cor-
respondence with the points and edges of G in such a way that two
points of T(G) are adjacent if and only if the corresponding elements

of G are adjacent or incident.

CHAPTER 2

Section 2.1
Homeomorphic Graphs
A collection of p points (O-simplexes) and q arcs
(l-simplexes) joining certain pairs of points which is embedded in
3-space in such a way that every intersection or arcs occurs only at
some of the p points is a finite geometric simplicial l-complex, or
simply a l-complex. Two l-complexes e] and éz are homeomorphic
if there exists a one-to-one bicontinuous mapping from 61 onto 62.
Since every graph is realizable as a l-complex and every l-complex
can be embedded in 3-space, there is at least one associated geometric
l-complex for every graph. This observation serves as the motivation

for defining two graphs to be homeomopphic with each other (or simply

 

homeomorphic) if their associated l-complexes are topologically

 

(a) ' (b) ' 1c)

 

 

 

Figure 2.l. Geometric l-complexes: (b) 15 homeomorphic With (C)
but not with (a).

equivalent, that is, homeomorphic. Each graph is then said to be a

homeomorph of the other. It is a consequence of this definition

 

(see [17]) that two homeomorphic graphs can differ only by the
number of points of degree 2 that they possess.
Another approach to the study of homeomorphic graphs involves

the concept of a subdivision (see [2], Chapter 8). An elementary

 

subdivision of a graph G is a graph obtained from G by the removal

 

of a edge uv of G and the addition of a new point w together with the
edges uw and vw. Occasionally we may describe an elementary sub-
division of G by stating that a new vertex w is inserted on the edge
uv of G, or that uv has been subdivided into the edges uw and vw.

A subdivision of G is a graph obtained from G by a finite sequence

 

of elementary subdivisions. Using this terminology, two graphs G1
and G2 are homeomorphic if either G1 = 62 or there exists a graph

G such that both G1 and G2 are subdivisions of G .

3
Sometimes it is useful to be able to determine when a graph

3

G2 which is homeomorphic with a graph G] is a subdivision of G].

We say that G2 is homeomorphic from G1 if either G2 = G] or G2 is

 

a subdivision of G]. In Figure 2.2, G1 and 63 are homeomorphic
graphs, neither of which is homeomorphic from the other, but both

are homeomorphic from G2.

10

 

 

 

Figure 2.2. Homeomorphic graphs.

Although the relation ”homeomorphic from" is not in general
symmetric, the slightly more general relation “homeomorphic with" is
clearly both symmetric and reflexive. We next verify that it is also
transitive, showing that this relation is an equivalence relation.
Before proceeding, however, we find it helpful to introduce some
additional notation. Whenever a pair of points u and v of a given
graph, neither deg u nor deg v being 2, are joined by r distinct u-v
paths having interior points only of degree 2, let these paths be
denoted by 03:), for 1 §_i 5_r.

To check the transitivity, suppose that the graph G1 is
homeomorphic with G2 and also that G2 is homeomorphic with G3. This
means, by definition, that there exist graphs G4 and G5 such that G1
and G2 are homeomorphic from G4 and that G2 and G3 are homeomorphic
from Gs. Now construct G6 from G2 by (1) replacing each 051) by
the edge uv if u and v are not adjacent, otherwise by a u-v path of
length 2, and (2) replacing each 03;) by a u-v path of length 2, for

i 3_2. Since applying a sequence of elementary subdivisions to a

ll

graph only increases the length of paths 05:), both G4 and G5 are
homeomorphic from G6. This implies that both G1 and G3 are also
homeomorphic from G6, hence G1 is homeomorphic with G3, and we have
established the fact that the relation "homeomorphic with" is an
equivalence relation on the set of all graphs.
Section 2.2
Homeomorphically Irreducible Graphs
We have seen in the preceding section that under the equivalence
relation "homeomorphic with“ all graphs are partitioned into classes,
with two graphs belonging to the same class if and only if they are
homeomorphic with each other. In [2], it is shown that in each such
equivalence class CE.there exists a unique graph H with the minimum
number of points of all graphs in this class. For convenience, we

include here a reproduction of that result and its proof.

Theorem 2.1. In every class C§.of homeomorphic graphs, there exists

a unique graph H such that if G66, then G is homeomorphic from H.

Epggf. Let<fL be a class of homeomorphic graphs and let H be a member
of 6 having the minimum number of points. For every graph G E (3,

G and H are homeomorphic, so that there is a graph H] such that both

H and G are homeomorphic from H]. Since H is homeomorphic from H],
either H = H] or H is a subdivision of H], the latter implying that

H] has fewer points than H (a contradiction because HIEE<f,). Hence

H = H], so that G is homeomorphic from H. It follows immediately

that H is unique.

12

In light of Theorem 2.1, we define a graph H to be

homeomorphicallygjrreducible, or simply irreducible, if whenever a

 

 

graph G is homeomorphic with H, then G is homeomorphic from H. By
Theorem 2.1, each irreducible graph serves as a canonical representa-
tive of the homeomorphism class to which it belongs.

There are several ways in which irreducible graphs can be
characterized; before presenting these, we introduce some additional
terms.

Two graphs G] and G2 are considered gggal_(written G1 = G2)

if they are isomorphic. A graph G is said to be less than G2,

1
denoted G1 < 62, if G] has fewer points than G2, or if they have

the same number of points and G1 has fewer edges than 62' If G1 is
less than or equal to G2 according to the above definitions, we write
G1 §_G2. We observe in passing that if neither G] < G2 nor 62 < G1
holds, it does not necessarily follow that G1 = G2.

The adjacency matrix of a graph G with p points Vi’

 

1 §_i 5_p, is the p x p matrix A = [aijJ’ where aij = 1 if Vi and

vj are adjacent and aij = 0 otherwise.

Theorem 2.2. For any graph G, the following statements are equivalent:
(1) G is irreducible.
(2) H a homeomorph of G implies G 5_H.
(3) No shortest path in G has an interior point of degree
two.

(4) Every point of degree 2 in G lies on a triangle.

l3

(5) If A denotes the adjacency matrix of G, then the matrix

A2 + A3 has no diagonal entry equal to 2.

3399:, (1) implies (2). Let G be irreducible, and suppose H is homeo-
morphic with G. Then H is homeomorphic from G, and either G = H or H
can be obtained from G by a sequence of elementary subdivisions. In
the latter case, H contains more points than G, so that G < H. Hence

G §_H in all cases.

(2) implies (3). Let G be a graph having the property that
whenever a graph H is homeomorphic with G, then G £.H- Suppose G has
a shortest path P containing an interior point w of degree 2, where,
say, w is adjacent to points u and v. Then by replacing the point w
together with the edges uw, wv by the single edge uv, a homeomorph H
of G is produced which has one less point than G, a contradiction.
Therefore, no such shortest path P can exist.

(3) implies (4). Let G be a graph in which every shortest path
contains no interior point of degree 2. Let w be a point of degree 2,
adjacent, say, to points u and v. If u and v are not adjacent, there
exists a shortest u-v path containing w as an interior point of degree 2.
Hence the three points u, v, and w determine a triangle.

(4) implies (5). Let G be a graph in which every point of
degree 2 lies on a triangle, and suppose the p points of G are
labeled vi, 1 5_i §_p. If A is the adjacency matrix of G, then it
is well known [9, p. 151] that the i,j entry of An is the number of

walks of length n between vi and Vj‘ In particular, the i,i entry

14

in A2 is simply the degree of Vi in G, while the i,i entry in A3

is twice the number of 3-cycles containing Vi’ Hence the i,i entry
in A2 + A3 is the sum of the degree of Vi and twice the number of
3-cycles containing vi. Clearly this entry has the value 2 if and

only if vi has degree 2 but lies on no 3-cycle. Thus no diagonal

entry in A2 + A3 can have the value 2.

(5) implies (1). Let G be a graph with adjacency matrix A,
and assume the matrix A2 + A3 has no diagonal entries with the
value 2. As we have just seen in the preceding paragraph, this is
equivalent to saying every point of degree 2 lies on a 3—cycle. If
G is not irreducible, then there exists a graph H different from G
such that G is homeomorphic from H. Hence at least one line of H has
been subdivided (one or more times) in the process of producing G.
This implies that G contains a point which is adjacent to exactly

two points which are not themselves adjacent, a contradiction. Thus

G is irreducible.

A point of degree 2 not lying on a triangle is called
suppressible. Thus Theorem 2.1 states that a graph G is irreducible
if and only if it possesses no suppressible point. As a simple
application of this, in Figure 2.2 only the graph 62 is irreducible.

Section 2.3
Some Properties of Irreducible Graphs .

In this section we investigate several graph-theoretic concepts

as they relate to irreducible graphs and their homeomorphs.

15

The connectivity K(G) of a graph G is the minimum number of

 

points whose removal either disconnects G or results in the trivial

graph consisting of a single point. We say G is n-connected if

 

K(G) 3_n. If G is irreducible and H is homeomorphic with G, and if
the removal of a certain set of points disconnects G, then the
removal of this same set of points disconnects H. Furthermore, if H
is not isomorphic to G, then H contains a point v of degree 2 so
that K(H) 5_2, as seen by removing the points of H adjacent to v.

These observations give our next result and its corollary.

Prpposition 2.1. If G is irreducible and H is homeomorphic with G,

 

then K(G) 3_K(H). Indeed, if G is not isomorphic to H, then
K(H) §_2.

Corollary 2.1. If G is 3-connected, then G is irreducible.

 

A graph is said to be n-colorable if it is possible to assign

 

to each point of G one color of a set of n colors so that every two

adjacent points are assigned different colors. The chromatic number

 

x(G) of G is the smallest value of n for which G is n-colorable.

If G is a graph whose chromatic number x(G) exceeds 2 and H
is a subdivision of G, then H differs from G only by the presence of
one suppressible point w for each elementary subdivision that was
performed upon G to yield H; a k-coloring of H is then produced by
assigning to each such suppressible point w of H any color which is

different from the colors of the two points adjacent to w. Such a

16

statement cannot be made, of course, if x(G) = 2 (for example,

consider a cycle of length 4). This can now be summarized as:

Proposition 2.2. If G is irreducible with X(G) 3_3 and if H is

 

homeomorphic with G, then x(H) 5.x(G).

Proposition 2.2 asserts that an irreducible graph G with
x(G) 3_3 has the largest chromatic number of all graphs in its
homeomorphism class 6?. Sharing the class Cf,with G is the bipartite
graph S(G) derived from G by performing one elementary subdivision
on every edge of G, so that x(S(G)) = 2. Thus each graph H E 6 has
chromatic number x(H) such that 2 5_X(H) 5_X(G). From this arises
the question of the existence of a graph H66 with X(H) = k for

every value of k where 2 < k < x(G).

Theorem 2.3. Let G be any (not necessarily irreducible) graph with
x(G) 3.3. Then there exists a graph H homeographic from G with

x(H) = k for each value of k such that 2 < k < x(G).

Proof. Put n = x(G) and let any n-coloring of G be given, n 3_4
(if n = 3, there is nothing to prove). The set of all points with

any one color is called a color class; thus the points of G are

 

partitioned into n color classes C1, C2, ..., C", any two of which
have at least one edge joining them. Let m be the minimum number

of edges joining any pair of color classes; denote any two color
classes joined by m edges as C and C'. Now obtain the graph G' from

G by performing one elementary subdivision on each of the m edges

l7

joining C and C'. Then a minimal (n-l)-coloring is achieved for G'
by placing the m new subdivision points in any class distinct from
C and C', and coalescing C and C' into one single class. Thus
x(G') = n-l.

Now if x(G') 3.4, repeat this procedure with G', obtaining
G" with x(G") = n-2. In this way we obtain a subdivision H of G

with chromatic number k for every value of k such that 2 < k < n.

Proposition 2.2 and Theorem 2.3 describe in general the
possible alteration in chromatic number of a graph produced by a
sequence of subdivisions. More specifically we may examine the
possible change in the chromatic number produced by a single elemen-
tary subdivision. It is not difficult to see that such a subdivision
H of G may result only in X(H) = x(G), x(H) = x(G) - 1, or
x(H) = x(G) + l, as illustrated by the elementary subdivision of a
path, 3-cycle, cn'4mcycle, respectively. Of course if X(G) 3.3,
then the discussion leading to Proposition 2.2 also shows that
x(H) 5.x(G). In the case where X(H) < X(G), an equivalent formula-

tion is given by

Theorem 2.4. Let x(G) 3_3. There exists an elementary subdivision

 

G' of G with x(G') = x(G) - 1 if and only if there exists a x(G)-
coloring such that for some two colors, precisely one edge of G joins

points having these colors.

Proof. Sufficiency. Assume that there exists a x(G)-coloring in

which for some two colors a and B, there is precisely one edge uv

l8

joining points u and v having these colors. Letting G' be the
graph obtained from G by the insertion of a new point w on the edge
uv, w can be assigned any color y distinct from a and B, and now all
a-colored and B-colored points can be colored alike, since in G' no
two such points are adjacent. Thus x(G') = x(G) - l.

Necessity. Let x(G) = k 3_3, let G' be any elementary sub-
division of G with x(G') = x(G) - l, and assume that for every k—
coloring and every pair of colors <1, 8, there exists at least two
edges joining points colored a and 8 (no x(G)-coloring can exist in
which there are two colors for which no edge of G joins points of
these colors). The set of all points of G are partitioned into k
color classes by every k-coloring. Let uv be the edge of G on which

w is inserted to produce G', and let u be any (k-l)-coloring of G'.

CASE 1. Assume u and v belong to distinct classes of n. Then w is
in a class distinct from those of u and v. But G can be reconstructed
from G' by replacing uw, w, and wv by the edge uv, so that p serves

as a (k-l)-coloring of G--a contradiction.

CASE 2. Assume u and v are in the same class of u. Then we may
introduce a new color class Cu containing only u; call this new
coloring u*. Now replace uw, w, and wv in G' by uv, reconstructing
G. Then u* is a k-coloring of G, but Cu is a color class joined to

only one other class by a single edge--again a contradiction.

Hence some k-coloring exists such that for some pair of colors,

exactly one edge joins points having these colors.

19

Corollagy 2.4. Let x(G) = 3. If G' is an elementary subdivision

 

of G with x(G') = 2, then all odd cycles of G share a common edge.

Proof. By Theorem 2.4, there is a x(G)-coloring in which some pair
of color classes have exactly one edge uv joining them. Since all
edges of G join points in distinct color classes, all odd cycles

(particularly 3-cycles) must pass through uv (see Figure 2.3).

 

 

GI

Figure 2.3. An example illustrating Corollary 2.4.

Another parameter which involves partitioning the point set

of a graph G is the point-outerthickness n(G) of G (denoted n3(G)

 

in [4]). For any graph G, n(G) is the minimum number of subsets con-
tained in every partition H of the point set of G, where the subgraph
induced by each subset is outerplanar. Such a partition H for G

consisting of exactly n(G) subsets will be henceforth referred to as

a minimal partition. Clearly if G' is any elementary subdivision of

 

G, then n(G') can exceed n(G) by at most 1 (a new partition H' can

20

be formed from an old minimal partition H by adding to H the singleton
subset consisting of the new suppressible point).

However, if n(G') = n(G) + l, and uv is the edge of G sub-
divided by w to produce G', then in each minimal partition H for G
there must be some subset SEEK to which both u and v belong (if u
and v belong to distinct subsets S, S' in H, then Sk){w} is outer-
planar and HL)[SL){w}] is a minimal partition for G' composed of
only n(G) subsets). Since the insertion of w makes the induced sub-
graph <S> nonouterplanar, then u and v must belong to some cycle in
<S> not containing uv. Then the insertion of w produces a subgraph
of <SLJ{w}> which is homeomorphic from K(2,3) (see[9],|3.107). Con-
versely, if u and v are situated as prescribed for every partition

of G, then n(G') = n(G) + 1. We summarize this as:

Propgsition 2.3. Let G' be the elementary subdivision of G produced
by subdividing the edge uv. Then n(G') = n(G) +1 if and only if each
minimal partition contains a subset in which u and v belong to a cycle

not containing uv.

The group T(G) of a graph G consists of the set of all iso-

 

morphisms of G under the operation of composition. Many of the basic
properties possessed by these groups can be found in [9, Chapter 14].
Here we discuss the relationship of the automorphism group of an
irreducible graph G with the automorphism group of a homeomorph of G.
We note that each point of a graph must map into a point of like

degree under isomorphism.

21

Many possibilities arise when one considers the orders of the
groups of an irreducible graph and one of its homeomorphs. For
example, if G is a path P2 with two points and if H is homeomorphic
with G, then |F(G)| = |F(H)| = 2. If G is a cycle of length 3 and H
is homeomorphic with G, then H is a cycle of length n for some n 3_3.
Hence, |F(G)[ = 6, while |F(H)| = 2n, so that |F(H)| 3_|F(G)|. For
the irreducible graph G of Figure 2.3 and the graphs H1 and H2 homeo-
morphic with G, we have [T(G)] = 2, |P(H])| = l, and |F(H2)| = 8, so
that lr(e)l > Ir1H])I but [T(G)l < IF(H2)I.

 

Figure 2.4. Homeomorphs H1 and H2 of an irreducible graph G having
|F(H])| < |F(G)| < |P(H2)|.

This uncertain situation can be remedied, however, by requiring that

G have no points of degree 2.

Theorem 2.5. If a graph G has no points of degree 2 (and so is
irreducible) and if H is homeomorphic with G, then T(H) is isomorphic

to a subgroup of T(G).

22

2599:, Since H is homeomorphic from G, the points of H consist of the
points of G together with the points of degree 2 resulting from how-
ever many elementary subdivisions are required to transform G into H.
If a denotes any isomorphism of H, then a must map the points of G
onto themselves, since the points of G have degrees other than 2.

Now let o' be the restriction of a to the set of points of G (so a'

is one-to-one since a is). To show that a' is an isomorphism of G,
consider any two adjacent points u and v of G. If u and v are also
adjacent in H, then d(u) is adjacent to d(v) so that o‘(u) is adjacent
to a'(v). If u and v are not adjacent in H, then the edge uv of G

has been subdivided, say u, u], ”2’ ..., un, v, in the process of

producing H. However, d(u), d(ul), d(uz), ..., d(u ), d(v) is a

n
path in H in which d(u.), i = l, 2, ..., n, is a point of degree 2;

1
thus this path is a subdivision of the edge a(u)a(v). Hence, in this
case, o'(u) is also adjacent to a'(v) so that a' is an isomorphism
of G.

Under any isomorphism of H, a path whose interior points have
degree 2 can only be mapped into a like path and the endpoints of
such a path must be mapped into the endpoints of the image path.
Therefore, each element aEF(H) uniquely determines an element o'e T(G),
and two distinct elements of T(H) produce two distinct elements of
T(G). From these observations and the manner in which the mappings

a' were defined, it follows that the set F' of all such mappings is

a subgroup of T(G) isomorphic to T(H).

23

Corollary 2.5. If a graph G has no point of degree 2, and if H is

 

homeomorphic with G, then |F(H)| 5.|F(G)|.

Pertaining to the area of traversibility, we say that a
graph G is eulerian if it contains a closed trail, called an eulerian
trail, which includes every edge of G exactly once and every point

at least once. A graph is hamiltonian if it has a cycle, which we

 

refer to as a hamiltonian cycle, which encounters every point of the

 

graph exactly once. A well-known theorem of Euler (see [9], p. 64)
states that a graph is eulerian if and only if it is connected and
every point has even degree. Thus for an irreducible graph H and any

homeomorph G of H, we have

Prpposition 2.4. If H is irreducible and G is homeomorphic from H,

 

then G is eulerian if and only if H is eulerian.

The statement obtained through the substitution of “hamil-
tonian" for “eulerian" in Proposition 2.4 is false, as can be seen
by taking H to be the graph made up of two 3-cycles sharing a com-
mon edge x and G obtained from H by inserting a new point on x.

Two rather more stringent traversibility requirements are

for a graph G to be randomly eulerian from appoint v65 G and to be

 

randomly hamiltonian from appoint vEEG. The first of these two

 

requirements means that G contains a point v such that the following
procedure always results in an eulerian trail: Begin at v and
traverse any incident edge. On arriving at a point, choose any

incident edge which has not yet been traversed. When no unused edges

24

are available, the procedure terminates. Analogously, G is randomly
hamiltonian from one of its points v if a hamiltonian cycle always
results from this procedure: Begin at v, proceed to any adjacent
point. 0n arriving at a point, select any adjacent point not
previously encountered. When no unused points remain, and an edge
exists between the final point chosen and v, the process terminates.
In 1951 Ore [12] characterized graphs which are randomly
eluerian from a point v as those graphs in which every cycle contains

v. The following result is an immediate corollary.

Proposition 2.5. If H is irreducible and G is homeomorphic from H,
then G is randomly eulerian from one of its points if and only if H

is randomly eulerian from one of its points.

As was the case with Proposition 2.4, the substitution of
"hamiltonian" for “eulerian" in Proposition 2.5 produces a false

statement, as illustrated by the example in Figure 2.5.

 

 

Figure 2.5. H is randomly hamiltonian from v, but possesses a sub-
division G which is not hamiltonian.

The example of Figure 2.5 prompts an additional remark about

homeomorphism equivalence classes. Although the irreducible graph of

25

a class containing infinitely many nonhamiltonian graphs may be
hamiltonian, the existence of one hamiltonian graph in a class
guarantees that the irreducible graph for that class is also hamil-
tonian (and similarly for the property of being randomly hamiltonian
from a point).
Section 2.4
Certain Homeomorphism Classes and the
Hamiltonian Index
A related aspect of the hamiltonian property is the hamil-

tonian index h(G) of a graph G. For any connected graph G, which is

 

not a simple path, h(G) is defined as the smallest nonnegative integer
n such that the iterated line graph Ln(G) is hamiltonian.

It is well known (see [9], p. 66) that every hamiltonian
graph is 2-connected and that every 2-connected nonhamiltonian graph
contains a subgraph homeomorphic from K(2,3). Thus the graphs homeo-
morphic from K(2,3), and, more generally, graphs homeomorphic from
K(2,n) (for n 3_3), provide an especially notorious class of non-
hamiltonian graphs. Consequently, for such graphs G, the value of
h(G) is positive. A natural question, then, to ask of a homeomorph
of K(2,n) is this: ls l the best possible lower bound, in general,
for h(G), and can the precise value of h(G) be determined? This

question is answered in the affirmative by our next result.

Theorem 2.6. Let G be any graph homeomorphic from K(2,n), n 3_3,

 

and let u and v denote the points of G having degree n. Then

26

1 if n is even.
h(G) =

d(u,v) - 1 if n is odd.
Proof. If G is homeomorphic from K(2,n) with n even, then u and v
are joined by an even number of paths, say P1, P2, ..., Pn’ so that
every edge of G appears in the trail constructed by travelling P1
from u to v, then P2 from v back to u, and so forth, exhausting all
n paths. In [3], a graph with the property that every edge of a graph

can be ordered in a sequence such that consecutive edges are adjacent

is called sequential and it is shown there that the line graph of a

 

graph is hamiltonian if and only if the original graph is sequential.
Thus h(G) = 1.

For G homeomorphic from K(2,n) with n odd, we proceed via
induction on d(u,v), where u and v denote the points of G with
degree n. If d(u,v) = 2, then at least one of the n paths Pi
(i = l, 2, ..., n) joining u to v in G, say P], consists of only two
edges x1 and x2. The line graph L(G) consists of two copies 8], B2
of Kn whose points are pairwise joined by n disjoint paths Pi' cor-
responding to the n paths Pi in G such that each path P1' in L(G)
has length one less than its counterpart Pi in G (see the following
diagram). Thus the path P]' in L(G) consists of a single edge x. A
hamiltonian cycle is then obtained for L(G) as follows: u], ”lu2’

P .

u2, 2 , v2, vzv], v], v1v3, P3', u3, u3u4, U4, P4', v4, ..., vn, Pn

un, unu], u]. Hence h(G) = l = d(u,v) - l.

9

27

 

 

,.. P' _..
I61- \\ X 1 // cv]\\
‘ 'V ‘. P' ' I
1u2°\'_/\/g—\_!/°v2 1
l ' ' I
U ' 1: l l l 2
1 l 1
l I PI | I
1 1 1
{UDM /—--O' Vn,‘
\ l
\’/ \_’l
G L(G)

Assuming that h(G) = d(u,v) - l for all homeomorphs G with
d(u,v) < k, we seek to verify that h(G) = d(u,v) - 1 when d(u,v) = k.
From G, construct G* by removing one edge from exactly one shortest
path of G; this yields d(u,v) = k - l in G*, so that G* falls under

the induction hypothesis, so that h(G*) = k - 2, implying that

Lk-2(G*) is hamiltonian. Now consider the k - 2nd line graphs of G

and G*. Since the shortest u-v paths present in G and 6* have lengths

k-2(

k and k-l, respectively, we are assured that Lk-2(G*) and L G)

each consist of identical subgraphs B1 and 82 joined by n disjoint

paths, the only distinction between them being that precisely one

k-2

path of L (G*) is a single edge x while the corresponding shortest

k-2

path in L (G) consists of two edges x1, x2 (see the figure below).

 

”~\l\.,___._.—-—-————O—/-o \\ I ""+ —————— fl; \
/ ‘ ’_»_’_,_.—1._. \ |l ._\_._ ________ \‘
I! B 1 " ”””” ’+'. B A I B f—‘L‘ ------ E B I
1 I ' ' i 1 : 2./ 1, 1: I I 1 E 2;
\ T J V

28

Although Lk‘2(

G*) is hamiltonian, no hamiltonian cycle of it contains
the edge x since such a cycle must also contain the other n-l paths
(possessing interior points) connecting B1 and 82, making an odd
number of disjoint paths that such a cycle must contain, which is

k-2(

impossible. Similar reasoning precludes L G) being hamiltonian,

as it contains an odd number of paths with interior points connecting

B1 to 82. However, Lk'2(G*) and Lk'2(G) can now be redrawn as shown
in the following figure.
Lk-2(G*) Lk-2(G)

Another result of G. Chartrand ([3] p. 562) states that if a graph
H contains a cycle C with the property that every edge of H is
incident with at least one point of C, then L(H) is hamiltonian.

The graph Li‘-2

(G) satisfies this condition, thus insuring that
L(Lk'2(e)) = Lk"(o) is hamiltonian. Hence h(G) = k - 1 = d(u,v) - 1.

This completes the proof.

To illustrate Theorem 2.6, consider the graph G1 composed

of 2 points joined by 3 disjoint paths of length 3 and the graph 62

29

consisting of 2 points joined by 4 disjoint paths of length 3. Then
h(G1) = 2 while h(Gz) = 1. If G]' and 62' represent the graphs
obtained from G1 and G2 by the insertion of an additional point into

each edge, then h(Gl') = 5 while h(GZ') = h(Gz) = 1.

CHAPTER 3

Section 3.1
The Nth Subdivision Graph and Its Structure

In 1965 Harary and Nash-Williams [10] introduced the concept

 

of the nth subdivision graph Sn(M) of a multigraph M. By definition,
this is a graph obtained from M by replacing every edge uv of M by a
u-v path of length n + l, where n 3_l. The graph S](M) is denoted
simply S(M) and is called the subdivision graph of M. Behzad [1], also
in l965, utilized the subdivision graph S(G) of a graph G in order to
characterize the total graph T(G) as isomorphic to the square of S(G).
While M ordinarily is not a graph, Sn(M) is always a graph; and if M
has p points and q edges, then Sn(M) is a (p + nq, (n + l)q)-graph.

The above definition for the nth subdivision graph could be extended

to the case where G is a pseudograph, but we shall not consider this

possibility since when n = l, S(G) may be a multigraph and not a graph.

0‘

M S(M) 52(M)
Figure 3.1. A multigraph M together with S(M) and 52(M).

30

31

We next consider some elementary properties of the subdivision
graph S(M) of a multigraph M. If we regard S(M) as obtained from M
by the insertion of one new point on every edge of M, then the original
points of M are nonadjacent in S(M) and form an independent set in
S(M). Since each new point is adjacent to exactly two old points, the
set of all the new points is also independent in S(M) and contains
only points of degree 2. It is clearly necessary, then, that for a
graph G to be a subdivision graph of a multigraph M, G must be
bipartite, and one of the two independent sets which partition the
point set of G contains only points of degree 2. We prove later that
this restriction is also a sufficient condition for a graph to be a
subdivision graph. Thus the only regular graphs which are subdivision
graphs are those that are 2-regular, namely those graphs which are
unions of disjoint cycles of even length. Of course, for n 3_l,
Sn(M) may contain odd cycles.

We next consider the question of deciding when a given graph
G is the nth subdivision graph of some multigraph M, and examine a
few simple choices for G. Certainly, (a) no nonempty complete graph
can be an nth subdivision graph, (b) every cycle Ck(n + 1), for k 3_3,
is isomorphic to the nth subdivision graph of Ck (for k = 2,
02(n + 1) = Sn(90) where 90 is the multigraph consisting of two points
joined by a pair of edges), (c) every path P(k _ l)(n + 1) + 1 is
isomorphic to Sn(Pk)’ and (d) the complete bipartite graph K(m,n) is

a subdivision graph if and only if at least one of m and n is 2.

32

Since we have already characterized 2-regular subdivison graphs
as unions of disjoint cycles, we now examine graphs containing at least
one point whose degree is different from 2. An uncomplicated criterion
for identifying those graphs which are nth subdivision graphs is pre-

sented as the following theorem.

Theorem 3.1. Let G be a graph which is not 2-regular. Then G is
h

 

the nt subdivision graph of a multigraph if and only if no block of
G is a cycle of length n + l and every ul-uz trail in G has a length
which is a multiple of n + l for all points u1 and u2 with deg ”i f 2,

for i = l, 2.

Epggf. Necessity. Let M be any multigraph and consider G = Sn(M).
In obtaining G from M, every edge uv of M is replaced by a path of
length n + 1. Thus every ul-u2 trail in G joining points u1 and u2
in M has length (k - l)(n + l), where k is the number of points of M
that appear in this trail. Since the only points of G which are not
of degree 2 are also points of M, then every u1-u2 trail in G joining
points u1 and u2 which are not of degree 2 has length that is a multiple
of n + 1. However, no block composed entirely by a ul-u1 cycle of
length n + 1, deg u.l f 2, can occur in G, since such a cycle corre-
sponds to a loop in M.

Sufficiency. Now let G be any graph, not 2-regular, with the
property that every u1-u2 trail joining points u1 and ”2’ which are
not of degree 2, has length a multiple of n + 1. We must show the

existence of a multigraph M such that Sn(M) = G. We may assume G

33

is connected, for otherwise the ensuing argument can be applied to
each component of G in order to construct the corresponding
component for M.

Select any point v1 in G which does not have degree 2. At
least one such point exists, since G is not 2-regular. Let V be the
set of all points in G whose distance from v1 is a multiple of n + l
and let U be the set of all other points. Thus, by hypothesis, all
points of G which are not of degree 2 belong to V so that U contains
only points of degree 2.

Every pair of points Vi’ vj of V are joined only by trails
whose length is a multiple of n + 1, for if Vi were joined to Vj by
a trail T0 of length d which is not a multiple of n + 1, then To,
together with trails T1, T2 from v1 to vi and from v1 to vj, forms
a v1-v1 trail whose length is not a multiple of n + 1.

Now let P1 and P2 be shortest paths from any point uEEU to
the set V, say to points Vi and vj in V. Inasmuch as the vi-vj

trail T formed by P1 and P2 has no interior point that is a point

of V, the length of T must be exactly n + 1. Furthermore, Vi # v\j

because if vi = Vj’ then all points of T except Vi have degree 2,

making T a block of G, a contradiction.

34

Thus every point u of U lies on some vi-vj path P1 j of length n + 1,

all of whose interior points are in U, joining two points of V. Each
point of U has degree 2, making it impossible for any point of U to
simultaneously lie on two such paths; thus each point uEEU uniquely
determines one of these v1-vj paths P. 1,1.
If we label all paths of length n + l joining each pair of
points v1, vj of V by P113, Pizi, ..., P(t), the desired multigraph

1sJ19J
M can now easily be described. The point set of M is the set V and
two points v1 and vj of M are joined by one edge x(kg for each path

19”}, k= 1, 2, ...,t.

All that remains is to verify that Sn(M) = G, that is, to
exhibit an isomorphism ¢ between Sn(M) and G. The point set of

Sn (M) is VLJV], where V1 consists of n points of degree two

"E5; 1, "(5i 2, ..., wi53,n for each edge xffg of M, with "(5; r( )
k

adjacent to w. for r = l, 2, ..., n - 1. In G each path P1 1

i,i M
of length n + 1 from v. to vj contains precisely n points of U, say

1
k k k k k
"(,3 1, u(,; 2, ..., u§,g n’ where u(,; r (’3 r+1

r = l, 2, ..., n - 1. Thus the mapping ¢ of S n(M) onto G defined

is adjacent to u

by the equations ¢(v.) = v. for v1€EV, ¢(w(k3 r) = u(kg r for

Wékg rEEV1s r = 1,2, ..., n. is one-to-one and adjacency-preserving.

This completes the proof of Theorem 3.1.

Corollary 3.1. Let G be a graph which is not 2-regular. Then G

is the subdivision graph of a multigraph if and only if every ul-u2
trail in G has even length for all points u1 and ”2 with deg U1? 2,
i = l, 2.

35

3399:, This corollary follows immediately from Theorem 3.1 with the
observation that when n = l, the hypothesis forbidding the presence
of a cycle of length n + l as a block of G is superfluous.

When a graph G is known to be an rnfllsubdivision graph of
some multigraph M, one might wonder if M is unique up to isomorphism;
that is, can G be the nth subdivision graph of two or more noniso-
morphic multigraphs? This question is settled in the negative by

the following:

Theorem 3.2. If M1 and M2 are connected multigraphs whose nth sub-

 

division graphs are isomorphic, then M1 and M2 are isomorphic.

Proof. It is convenient to deal first with connected multigraphs
M1 and M2 having 3 or fewer points and which have isOmorphic nth
subdivision graphs. If we temporarily agree to call the multigraph

Go a cycle, then whenever Sn(Ml) = 5 (M2) is 2-regular, namely a

n
cycle, then M1 and M2 must also both be cycles, necessarily with the
same number of points, and hence isomorphic. If Sn(M]) = Sn(M2) is
not 2-regular, then it contains a point of degree k f 2. Since the
only points of Sn(M]) and Sn(M2) not of degree two are those points
which are in the original multigraph, consequently M1 and M2 must
pggp consist of one point v joined by k edges to precisely those
points connected to v in the nth subdivision graph by a path of
length n + 1.

Next we consider connected multigraphs M1 and M2 having more

than 3 points with Sn(Ml) = Sn(M2)‘ The remainder of this proof was

36

suggested by an elegant analogous proof for line graphs given by
Jung [12]. For any isomorphism ¢1 : Sn(M]) + Sn(M2), we shall exhibit
an induced isomorphism ¢ : M1 +-M2.

Suppose v is any point of M1, and let E(v) be the set of all
edges incident to v. We claim that to every véEM1 there is exactly
one point v' in M2 such that E(v) + E(v') under ¢]- If deg v 3_2,
let x1 and x2 be edges at v and let v' be the common point of edges
¢](x1) and ¢1(x2). Then for each edge x at v, v' is incident with
¢](x); and for each edge x' at v', v is incident with ¢'1(x'). If
deg v = 1, let x = uv be the edge at v. Then deg u 3_2, hence E(u)
corresponds to E(u') and ¢](x) = u'v', where v' = ¢](v). Since for
every edge x' at v', the edges o'}(x') and x have u as a common
point and u' is on x', therefore x' = ¢1(x) and deg v' = 1. Thus in
all cases there is precisely one v' in M2 for each v in M1 such that
E(v) + E(v') under 6]; call this induced mapping ¢- Then ¢ is evi-
dently one-to-one on the point sets of M1 and M2 since E(u) = E(v)
only if u = v. Also o is onto, since to any point v' in M2 there
exists an incident edge x' which determines an edge o'}(x') in M1,

one of whose endpoints maps into v'. The adjacency-preserving

property of t is inherited from ¢], and the proof is complete.

One useful benefit which we can derive from Theorem 3.2 is
that since each nth subdivision graph G is obtained from only one
multigraph M (up to isomorphism), then we can always regard M as
obtainable from G by the procedure used in the proof of Theorem 3.1.

Furthermore, if G is an nth subdivision graph of a graph M, we can

37

regard G as composed of an independent subset V of points v1, v2,

..., v together with certain v1-vj paths P11 of length n + l,

t
where each edge in G belongs to some P11. and no more than one path

. “oins v. and v..
J J 1 J

A related question is whether there exist nonisomorphic multi-

P.
1

graphs M1 and M2 with Sm(M]) = Sn(M2) for m f n. This can occur as
is seen by taking m = 2, n = 3, M1 = P5, and M2 = P4 (or M1 = C4,

and M2 = C3). A more general example of this is obtained by taking
M1 = Sn(M) and M2 = Sm(M) for any multigraph M and distinct integers

m and n; then Sm(M]) = Sm(sn(M)) = Smn+m+n(M) = Sn(Sm(M)) = S (M

n 2)

and M1 and M2 are nonisomorphic graphs.
Although each acyclic block of a graph G gives rise to n + l
acyclic blocks in Sn(G), the next proposition shows that G and Sn(G)

have the same number of cyclic blocks.

Proposition 3.1. The set of cyclic blocks of Sn(G) is {Sn(B1)} where
{Bi}’ 1 = i, 2, ..., k, is the set of cyclic blocks of G.

3529:, Suppose that B' is any cyclic block of Sn(G) and denote
those points of B' which are also points of G by v1, v2, ..., Vr'
We claim that the induced subgraph <v1, v2, ..., Vr> = B of G is a
cyclic block whose nth subdivision Sn(B) equals 8'. One way to show
that B is a cyclic block is, for every three distinct points of B,
to exhibit a path joining any two of them which does not contain the

third (B surely contains three or more points since 3' cyclic implies

that 8' contains a cycle which is an nth subdivision of a corresponding

38

cycle in G). For each trio of points u, v, w of B, there is a path
P' in B' joining u to v which does not contain w, by virtue of B'

being a cyclic block. Since B' is a subgraph of an nth subdivision
graph, P' has length a multiple of n + 1 and is of the form u, u0,1,

110,2, ..., ”0,", U], U],-l, 111,2, ..., “1,11, U2, ..., utfll’ Ut+1= V.

Thus in B, the path P : u, u], ”2’ ..., ut, u = v joins u and v,

t+l
omitting w.

Now let B be any cyclic block of G and consider the subgraph
B' = Sn(B) of Sn(G). To demonstrate that B' is a cyclic block of
Sn(G), it suffices to show that each pair of points of B' lie on a

common cycle. Letting u and v be any two points of B', we distinguish

three cases concerning them.

CASE 1. If both u and v are points of B, then since B is a cyclic
block, there exists a cycle C containing both u and v; thus Sn(C) is

a cycle in 8' containing both u and v.

CASE 2. If exactly one of u and v is not a point of B, say u, then

u is an interior point of a ul—u2 path P' of length n + l in B' where
u1 and u2 are points of 8. Since u], v, and u2 all belong to the
block B, there exists a ul-v path P] not containing u2 and a v-u2
path P2 not containing u]. Thus in B', the paths P', Sn(P1), and

Sn(P2) form a cycle containing u and v.

CASE 3. If neither u nor v is a point of B, then in a manner almost
identical to the approach employed in CASE 2, a cycle can be con-

structed in B' which is common to u and v.

39

Thus every cyclic block B1 of G gives rise to a cyclic block
Sn(Bi) of Sn(G) and, conversely, each cyclic block Sn(B1) of Sn(G)
corresponds to precisely one cyclic block B1 of G.

If we restrict our attention to those graphs G for which
G = S(H) for some graph H, we obtain several additional equivalent

conditions.

Theorem 3.3. Let G be a graph which is not a union of disjoint
cycles. Then the following statements are equivalent:
(1) G is the subdivision graph of a graph.
(2) G does not contain K(2,2) as a subgraph and every
ul-u2 trail in G has even length for all points u1
and u2 with deg u1 # 2, i = 1, 2.
(3) G is bipartite having a point set which is a dis-
joint union of independent sets U and V such that
U contains only points of degree 2 and no two points
in U are mutually adjacent to the same two points of

V.

3599:, Throughout the proof we shall assume G is connected since

if the theorem holds for every component of G, it holds for G itself.
(2)==>(l). Since a connected graph which is not a cycle

cannot be 2-regular, G satisfies the hypothesis of Corollary 3.1.

It remains to be checked that by forbidding the presence of K(2,2)

as a subgraph of G we guarantee that the multigraph M constructed in

the proof of Theorem 3.2 is actually a graph. Referring to the

40

construction of M in the sufficiency portion of the proof of
Theorem 3.1, we find that the only way that one pair of points v1,

v. can be joined by two lines x! ., x? . in M is by the occurrence

J 1 J 1:3

of at least two paths P11}, P12; of length 2 from v1 to vj in G.

But these paths Pili’ P§?g together form the subgraph K(2,2) in G.
Thus every pair of edges in M with common endpoints corresponds to
a K(2,2) subgraph of G.

(1)==>(3). For any point v1 of G which is not of degree 2,
we define V as the set of all points of G having even distance from
v1 and U as the set of all other points of G. Then, as in the proof
of Theorem 3.1, all points of U have degree 2 and both U and V are
independent sets, implying that G is bipartite. Again referring to
the construction of M such that S(M) = G detailed in the proof of
Theorem 3.1, no two points of U can be interior points of two paths
P11}, P§?; joining the same pair of points v1, vj of V since this
would mean that in the graph M v1 and vj are joined by 2 edges.

Hence no two points of U are mutually adjacent to the same pair of
points of V.

(3)==>(2). If G is a bigraph whose point set is partitioned
into subsets U and V such that U contains only points of degree 2,
then every vl-v2 trail, where v1 and v2 are not 2-valent, joins points
in V and hence has even length. Thus by Corollary 3.1, G is the sub-
division graph of a multigraph M. A repetition of the same argument

given in the preceding paragraph suffices to show that no multiple

edges can occur in M; that is, M is a graph.

41

Corollary 3.3a. A graph G is the subdivision graph of Kn’ n 3_2,

 

if and only if G is a bipartite graph, containing no 4-cycle, and whose
point set can be partitioned into two independent subsets composed of

n points of degree~n - l and (3) points of degree 2.

3599:, First we show that the above condition is sufficient. By
Theorem 3.3(3), G = S(H) for some graph H. Assuming that the above
condition holds, it remains to be shown that H = Kt for some integer
t 3_2. If H is a (p, q)-graph, then G has p + q points and 2q edges.
Since each edge of G is incident with exactly one of the n points of
the independent set V, we have that 2q = n(n - l), or that q = 91575—11
= (3). All of the p + q points of G lie in U V, thus p + q = (g)+ n
implies that p = n. Hence H is the complete graph on n points. The

necessity follows immediately.

Corollary 3.3b. A graph G is the subdivision graph of the complete

 

bipartite graph K(m,n) if and only if G contains no 4-cycle and the
point set of G is the disjoint union of independent sets U, V, and W,
composed respectively of mn points of degree 2, m points of degree n,

and n points of degree m.

Egggj, The necessity is immediate. To show that the above condition

is sufficient, we note that Theorem 3.3(3) guarantees that G = S(H)

for some graph H; it remains to be seen that H = K(s,t) for some pair of
positive integers s and t. If H is a (p, q)-graph, then G has p + q

points and 2 q edges. Summing the degrees of all the points of G, we

42

find that 2q = l/2(2mn + mn + nm), or that q = mn. Then p + q =
mn + m + n implies that p = m + n. Hence H = K(m,n).
Section 3.2
Properties of Nth Subdivision Graphs
Since a graph G and its nth subdivision graph Sn(G) belong

to the same homeomorphism equivalence class, they possess many
common characteristics. Although such concepts as order or the
number of edges are obviously not preserved, planarity and the
invariance of the number of connected components is maintained.

Outerplanarity, on the other hand, is not in general inherited by

Sn(G) from G, as shown by K4-x and it subdivision graph.

S(K4-x)

 

f

Figure 3.2. An outerplanar graph K4-x and its nonouterplanar sub-
d1v151on graph.

It is possible to completely delineate those nth subdivision
graphs which are outerplanar, as shown by our next theorem; before
Proceeding, however, we present a definition.

A gpgtg§_is a connected graph every block of which is either

a (zycle or K Within the context of nth subdivision graphs, the

2.

43

concepts of cacti and outerplanar graphs coincide, as we now

see.

Theorem 3.4. Let G be an nth subdivision graph. Then G is outer-

 

planar if and only if every component of G is a cactus.

Erggf, Since the sufficiency is evident, we proceed directly to
the necessity portion of the proof. We may assume that G is a
connected outerplanar nth subdivision graph, for otherwise we may
consider the individual components of G. Moreover, we may also
assume that G contains at least one point not of degree two since
the theorem holds for 2-regular connected outerplanar nth subdivision
graphs, i.e., disjoint unions of cycles. To verify that G is a
cactus, we proceed via induction on the order of G. The theorem is
immediate for connected nth subdivision graphs on three or fewer
points. Assuming that every outerplanar connected nth subdivision
graph with fewer than p points is a cactus, we consider such a graph
G on p points.

The blocks of G having 3 points or less are either single
edges or 3-cycles, and both types are cacti. Accordingly, we let 8
be any block of G having 4 or more points. We may regard the nth
subdivision graph G, by means of the construction given in the proof
of Theorem 3.1, as having a point set made up of two subsets U and
V, where all noncarriers are contained in V and all points of U have

(k

degree 2, and where all the edges of G occur in paths P1 1 of length

n + l joining distinct points v1, v1 in V. Since 8 is a cyclic block,

44

it contains a point of U which is an interior point of some such path
P of length n + l joining two points u and v of V; u and v are also
points of B. Denote the subgraph obtained from G by deleting the n
interior points of degree 2 of the path P as 6*. Note that G* is an
nth subdivision graph since all ul-u2 trails in G* joining points u1
and u2 not of degree 2 (which are elements of the set V) have length
a multiple of n + 1. To be sure, G outerplanar implies the subgraph
G* is outerplanar; thus by our induction hypothesis, 6* is a cactus.
In the block B, the points u and v belong to a common cycle C.
If we can demonstrate that C comprises all of B, then we will have
shown that every block of the graph G is either a cycle or a single
edge, so that G is indeed a cactus.
For every three distinct points of B, there exists a path
joining any two of them which excludes the third. Thus B contains
a u-v path P' which is disjoint from the path P. No two points of
P' lie on a cycle in 6* because this would generate a subgraph
homeomorphic from K(2,3) in B, contradicting the outerplanarity of
G. Thus the cycle C is composed of the paths P and P', so that we
can label C by u, u], ”2’ ..., u , v = wo, w], "2’ ..., wk_], wk = u,

n
where the u., l 5_i 5_n, are carriers in P and the w1, O §_i §_k,

1
are the points of P'.

If 8 contains a point w not belonging to C, then again by
utilizing the criterion of the first sentence in the preceding para-
graph, we can find paths P", P"' joining w to distinct points W1.

wj of C (if every path from w to C joins w to the same point w1,

then w1 is a cutpoint of B).

45

--
-
Q

 

But this implies the existence of a cycle in G* containing the two
points w1 and "j of P', which we've already seen is impossible.
Therefore C passes through every point of B. This completes the

proof.

Section 2.3 of Chapter 2 contained a discussion of various
characteristics of a graph G and any subdivision H of G, in particular
their chromatic numbers and their automorphism groups. The remainder
of this section is devoted to obtaining more precise results in these
two areas when H = Sn(G).

Proposition 2.2 of Chapter 2 states that if G is irreducible,
with chromatic number x(G) 3_3, then for any graph H in the same homeo-
morphism class with G, we have 2 §_X(H) 5_x(G). In particular, for
all positive integers n, we have 2 §_ X(5n(G)) 5_X(G). This inequality

can in general be greatly improved, as our next result shows.

46

2 if n is odd.
Theorem 3.5. Let x(G) 3.3. Then X(5n(G)) =

 

3 if n is even.
Proof. Suppose the point set of G is partitioned into x(G) = k color

classes C], C , Ck, where k 3_3.

2, ...
For odd values of n, say n = 2r - l with r = l, 2, 3, ...,
Sn(G) is obtained from G by inserting new points u], u2, ..., ”Zr-l
into each edge uv of G. A minimal 2-coloring of Sn(G) is then
achieved by assigning color a to the points of the type ”2’ U4, ...,
”Zr-2 and also to the points of Sn(G) which are in G, and color 8 to
points of type u], u3, ..., ”Zr-1'
When n is even, say n = 2r with r = l, 2, 3, ..., X(G) > 2
implies the existence of at least one cycle of odd length 5 in G
(since every pair of color classes are joined by at least one edge).
Thus in Sn(G) there exists at least one cycle of odd length s(2r + 1),
so that X(5n(G)) > 2. Now Sn(G) is obtained from G by inserting 2r
points u], "2’ ..., ”2r into each edge uv of G; if the points of
Sn(G) which are in G are assigned color a, points of the type u],
u3, ..., ”Zr-l are colored 3, points of the type ”2’ U4, ..., ”Zr-2

are colored a, and u2 is colored y, then we have produced a 3-

r
coloring of Sn(G). Hence X(Sn(G)) = 3.

For any irreducible graph G, Theorem 2.5 guarantees that
T(Sn(G)) is isomorphic to a subgroup of T(G). In the specific case
concerning nth subdivision graphs, this result can be strengthened

considerably.

47

Theorem 3.6. For any graph G, no component of which is a cycle,

F(Sn(G)) is isomorphic to T(G) for every positive integer n.

Proof. As in the proof of Theorem 3.1 and the remarks following
Theorem 3.2, both G and Sn(G) can be regarded as consisting of an

independent set V of points v1, v2, ..., v with one path P1. of

t J

length n + l joining v1 to Vj in Sn(G) whenever the edge Vivj is

j has interior points of degree 2 only,

so that under any automorphism a of Sn(G), each path Pij must map

present in G. Each path P1

into a like path and the endpoints of P11 must be mapped into the
endpoints of the image path. (If any interior point u1 of some path
P11 maps into a point vjEEV, then deg Vj = 2 and since the component

of G containing vj is not a cycle, there exists a point vkEEV with

deg vk f 2. Then dSn(G)(Vj’ vk) E O mod(n + 1) and dSn(G)(ui’ Vj) z
0 mod(n + 1). Hence dSn(G)(ui’ vk) i 0 mod (n + l), but
dsn(G)(o(u1), d(vk)) = dSn(G)(vj’ a(vk)) E 0 mod(n + l), inasmuch
as d(vk)€EV, contradicting the assumption that o is an automorphism.)
Thus each element a€F(Sn(G)) uniquely determines an element a'E I‘(G),
and conversely. From this observation and the way in which these
automorphisms are defined, it follows that T(G) and P(Sn(G)) are
isomorphic.
Section 3.3
Factorization in Sn(G)
An r-factor of a graph G is a nonempty spanning subgraph of

G which is regular of degree r 3.1. If a graph G can be expressed

48

as an edge-disjoint union of r-factors, we say that G is r-factorable.

 

Clearly a graph G may have an r-factor without being r-factorable.
Inasmuch as Sn(G) always contains points of degree two, we shall deal
only with the question of the existence of a l-factor, or a 2-factor,
for Sn(G) and certain other related graphs.

It is immediate that a necessary condition for a connected
graph G to contain a l-factor is that G have even order. It is
easily seen that this simple condition in general is not sufficient; for
example, the complete bipartite graph K(l, n-l), for n an even integer
(n > 2), does not contain two nonadjacent edges, much less n/2 such
edges.

We continue our discussion of factorization with an elementary
observation which will be used in the sequel. A path or cycle on n

points is denoted by Pn or C", respectively.

Proposition 3.2. For k = l, 2, 3, ..., the path P2k has a unique

1-factor while the cycle C2k has exactly two 1-factors.

Proof. For any path P2k : v1, v2, ..., V2k’ the unique l-factor must
consist of the edges V1V2’ v3v4, ..., V2k-lv2k' In the case of the
cycle C2k : v1, v2, ..., v2k, v], in addition to the aforementioned
set of edges, the edges v2kv], v2v3, ..., V2k-2v2k-l also form a
l-factor.
Obviously P2k is not l-factorable, while C2k is l-factorable.
Whenever a graph G possesses a l-factor F, it follows that

Sn(G) also has a l-factor provided that n is an even positive integer.

49

To verify this assertion, it is helpful to observe that if the point
set of G is V = {v1, v2, ..., vp}, then Sn(G) consists of the set V
together with q disjoint vivj paths P11 of length n + l, where each
path Pij 1n Sn(G) corresponds to the edge Vivj in G. In $2k(G)’ each
path which corresponds to an edge x1 of G in F has odd length, hence
possesses a unique l-factor F1, for i = l, 2, 3, ..., p/2. Letting
F6 denote the set of all edges of the form u21_]u21, for 1 = l, 2,

3, ..., 2k, 1n all paths P11 : v1, u], ”2’ ..., u2k, vj wh1ch cor-

P/Z
respond to an edge of G not in F, K.) F1 is the desired l—factor of

i=0
$2k(G).
Conversely, if $2k(G) possesses a l-factor F, a l—factor for
G is formed by all edges Vivj corresponding to those Vi‘vj paths
P11 in S2k(G) which contain an edge x1€EF incident with v1 (notice

that two paths Pij’ Pik cannot both contain an edge from F which is

incident with v1). Thus we have shown

Theorem 3.7. A graph G has a 1-factor if and only if $2k(G) has a

l-factor, where k = l, 2, 3, ....

We next consider the question of deciding when an odd sub-
division graph 52k-1(G) has a 1-factor, for k = 1, 2, 3, .... The

following lemma reduces this question to a simpler one.

Lemma 3.1. For any graph G and positive integer k, 52k-1(G) has a
l-factor if and only if S(G) has a l-factor.

50

23921. Let V = {v1, v2, ..., vp} be the point set of G. Then S(G)
and 52k-1(G) each consist of the set V together with exactly one
v1-vj path of length 2 or 2k, respectively, whenever v1vj is an edge
of G. To any l-factor of S(G), there is an associated l-factor F'
of 52k-1(G) obtained in the following way. In S(G), each point v1
is incident with exactly one edge x1€EF and this edge lies in
exactly one v1-vj path P13. Labelling the corresponding v1-vj path
P..' in $2k-1(G) as v1, u], ”2’ ..., u2k_], vj, let F' be the set

lJ

{Viu'ls U2U3, ..., "ZR-ZUZk-1}‘ Then F' = .HIFi' 15 a 1-factor 0f

52k-1(G)' Of course, if $2k-1(G) has a l-factor for each positive

integer k, then by taking k = l, we have that S(G) has a l-factor.
One additional definition is needed in dealing with the ques-

tion of the existence of al-factorfor 52k-1(G)° A connected graph

is called unicyclic if it contains precisely one cycle.

Theorem 3.8. For any graph G and positive integer k, 52k-1(G) has

 

a l-factor if and only if each component of G is unicyclic.

3592:, By Lemma 3.1, it suffices to show that S(G) has a l-factor

if and only if each component of G is unicyclic. In showing the
necessity of this condition, we follow a suggestion of J. Zaks. If

G has a component C which is not unicyclic, then the number of points
p of C is not equal to the number of edges q of C (a connected (p, q)-
graph is unicyclic if and only if p = q). All edges of the bipartite
component S(C) of S(G) are of the form u1vj, where u], ”2’ ..., u

P
and v1, v2, ..., vq correspond to the points and edges, respectively,

51

of C. Thus any l-factor of S(C) is composed of nonadjacent edges
"ivj’ implying that there is a one-to-one correspondence between the
u. and the Vj' But this means that p = q, a contradiction. Hence

1
each component of G is unicyclic.

Conversely, assume that each component of G is unicyclic and
consider any component C' of S(G), where C' = S(C) for some component
C of G. Then C unicyclic implies that C' is unicyclic; denote the
unique cycle in C' by Z : v], u], v2, ”2’ ..., Vt, ut, v], where
the points v1 correspond to points in C and deg u1 = 2, for i = l,

2, ..., t. As in Proposition 3.2, Z = C2t has a l-factor F0. C' - Z
is a union of trees Tk, for k = l, 2, ..., r, where each tree Tk
contains a point wk adjacent to some point vj of 2 with deg Vj # 2.
The distance d(u,v) in C' = S(C) between points u and v, neither of
whose degrees is 2, is always even; thus the distance d(wk,v) in Tk’
where deg v f 2, is always odd. This implies that Tk has a unique

l-factor Fk composed of all edges uv in Tk’ where d(wk,u) is odd and

r
d(w .V) is even. Then F = \,)F
k k=0

k is a l-factor for S(G).

Corollary 3.8. Let G be a connected (p, q)-graph and k a positive

 

integer. Then 52k-1(G) has a l-factor if and only if p = q.

In general, the existence of a l-factor for a (p - q)-graph
G is independent of the existence of a l-factor for S(G), even if we
restrict our attention to connected graphs G having both p and q even.
This lack of relationship is illustrated by the following four infinite

classes of connected graphs. For each positive integer i, if G1 is

52

the cycle C 2, then G1 has a l-factor, as does S(G1), since G1 is

2i+
unicyclic. Taking G1 as the cycle C21+2 together with edges wv1 and
wv2 joining any point w of C21+2 to two additional new points v1 and
v2, we find that G1 has no l-factor, although S(G1) does. In Figure

3.3, the remaining two situations are illustrated.

 

/
/
I
K
\
C2i+1
(a) Graphs 61 = W21+2 having (b) Graphs G1 having no
a l-factor while S(Gi) l-factor and such that
has no l-factor. S(G1) also has no

1-factor.

Figure 3.3. Graphs G such that S(G) has no l-factor.

Choosing 61 as the "wheel" W21+2 of Figure 3.5(a), it is easy to
find a l-factor of G1, but S(Gi) has no 1-factor. If G1 consists

of three copies of C 1 joined by single edges with a new point v,

21+
as in Figure 3.5(b), then neither 61 nor S(Gi) possess a l-factor.

53

A criterion for Sn(G) to be l-factorable is much easier to
establish than a test for the existence of a l-factor. For Sn(G) to
be l-factorable, it must be an edge-disjoint union of l-factors F1,
F2, ..., Ft’ so that Sn(G) is regular of degree t. Thus t = 2, imply-

ing that Sn(G), and G as well, is a disjoint union of cycles. We

summarize this as

Proposition 3.3. For any graph G, Sn(G) is l-factorable, for n 3_l,

if and only if each component of G is a cycle.

For any graph G, the total graph T(G) is related to the sub-
division graph S(G) by the equation T(G) = 52(6). We shall make use
of this to develop necessary and sufficient conditions for T(G) to
possess a l-factor.

In order for the nth power Gn (n 3_2) of any graph G to have
a l-factor, Gn must possess an even number of points. The partner-
ship of G. Chartrand, A. Polimeni, and the author was able to prove
that this simple necessary condition is also sufficient for Gn to have

a l-factor.

 

Theorem 3.9. Let G be an arbitrary graph. Then Gn (n 3_2) has a

l-factor if and only if each component of G has even order.

Proof. It suffices to show that G2 has a l-factor if and only if G

has even order, inasmuch as Gn (n 3_2) and G share the same point set.
We may further assume that G is a connected graph, for otherwise we

may apply the following argument to each component of G.

54

The necessity of the given condition being obvious, we proceed
to the sufficiency portion of the proof. Letting the order of G be
2n, the proof is by induction on n. For connected graphs on 2 points,
the assertion is obvious. Assuming the assertion is true for all
appropriate graphs on fewer than 2n points, we consider a connected
graph G with order 2n. We may further assume that G consists of two
or more blocks, for if G is a single cyclic block, then G2 has a
hamiltonian cycle (see [8]), alternate edges of which furnish a 1-

factor. It is convenient to distinguish two cases.

CASE 1. G contains a cyclic endblock 8. Suppose that v is the cut-

 

point of G in B. In [6], it is shown that for any cyclic block B with

2

at least 4 points, 8 - u is hamiltonian for any u B. Thus if B

contains an odd number p of points, P 2.5, then B2 - v is hamiltonian

and has an even number of points; hence there is a l-factor F0 for

2

B2 - v. If B has exactly three points, then B - v is simply a copy

of K2, and therefore is a l-factor, say F0. Also the connected graph

G' = G - (B - v) has an even number of points, so that by the induction

assumption there is a l-factor F1 of (G')2.

of 62.

Then FOUF1 is a l-factor

CASE 2. Each endblock of G is acyclic. Let v denote a cutpoint of

 

G such that all blocks containing v, except at most one, are endblocks.
If there are at least two endblocks vv1 and W2 containing v, then the
connected graph G' = G - {v],v2} has an even number of points and by

the induction assumption, (G')2 has a l-factor F. Since the edge vlv2

55

is present in Gz, FL}{v]v2} is a l-factor of G2. In the event that
there is just one acyclic endblock vv1 containing v, let 8 be the other
block containing v. Then G' = G - {v,v]} is connected and has 2n - 2
points, so that the induction hypothesis implies that there is a
l-factor F for (G')2. Then FlJ{vv]} is a l-factor of G2. This com-

pletes the proof of the theorem.

Corollary 3.9a. Let G be a connected (p,q)-graph. Then T(G) has a

 

l-factor if and only if p + q is even.

 

T(G)
Corollary_3.9b. Let G be a connected graph. Then n
T(G) G (n 2_ 2)
has a l-factor if and only if has even order.

Gn (n 3.2)

An interesting special case of Corollary 3.9a occurs when G

' = M 2: +1
15 the complete graph Kp. Here we have q 2 and p + q E-(Ez—A,

so that we may conclude that T(Kp) has a l-factor if and only if
p E O or 3 (mod 4).

Whenever a graph H has a 2-factor, by definition it contains
a collection of disjoint cycles C1, C2, ..., Ck which span H. If H
is an nth subdivision graph Sn(G) of a graph G, then it turns out

that Sn(G) is composed of these cycles only.

Theorem 3.10. For any graph G, Sn(G) has a Z-factor if and only if

each component of G is a cycle.

Proof. We may assume G is connected, for otherwise we may work with

each component separately. Suppose first that Sn(G) has a 2-factor

56

F; then F is a collection of disjoint cycles C1, C2, ..., Ck which
span 511(6). Now if any point u EC] is adjacent to a point VEC],
then deg v 313 implies that v corresponds to a point of G, so that
deg u = 2. But then the cycle C1 containing u must also contain v,
which means that C1 = C], violating the choice of u. Thus k = 1,
that is, C1 is a spanning subgraph of Sn(G). Furthermore, if two
points v1 and v2 in C1 are joined by a diagonal edge (an edge not
belonging to C] which joins two points of C1), then deg v1 f 2 for
i = l, 2; this is a contradiction since by Theorem 3.1, every vl-v2

path has length at least n + 1. Thus C = Sn(G) implies that G is

1
also a cycle. The converse is immediate.

Corollary 3.10. The following statements are equivalent for any
graph G:

(l) Sn(G) is l-factorable.

(2) Sn(G) is 2-factorable.

(3) Each component of G is a cycle.

Section 3.4
The Enumeration of Trees Having a l-Factor

In the course of this research a considerable number of
enumeration problems have arisen. Some of these problems, for
example the enumeration of homeomorphically irreducible trees, have
been dealt with elsewhere (see [11]). Although extensive considera-
tion of the area of graphical enumeration is beyond the focus of this
dissertation, we do present one such problem as an example: the

number of trees of given order which possess a l-factor.

57

Before proceeding further, we require some additional

definitions. A rooted graph is a graph in which one of its points,

 

called the root, is distinguished from the others. Thus two rooted
graphs are isomorphic if there exists a one-to-one correspondence

between their vertex sets which preserves not only adjacency, but

also the roots. I

 

h—z

Figure 3.4. The 10 nonisomorphic rooted trees of order 6 or less
having a l-factor.

The generatinggfunction T(x) for rooted trees possessing a
l-factor is defined as T(x) = iaZkXZk, where a2k is the number of
nonisomorphic rooted trees of :rJer 2k having a l-factor. The
generating function t(x) for (unrooted) trees possessing a l-factor
is similarly defined ad t(x) = ib2kx2k, where b2k is the number
of nonisomorphic trees of orderk2A having a l-factor. Figure 3.4

displays the nonisomorphic rooted trees of orders 2, 4, and 6 which

58

have a l-factor--each tree has the edges of its l-factor darkened

and its root encircled. Thus by direct observation we conclude that

T(x) = x2 + 2x4 + 7x6 + ....

E. M. Palmer has suggested an approach originated by P61ya
[l6] and refined by Otter [14], details of which can be found in
Chapter 3 of [11], which shows that T(x) and t(x) satisfy the follow-

ing functional equations:

21

T(x) V x), and

 

11x) - 1/2111x) - V(le)

w k
T(x
where V(x) = x exp Z—E—A .
k=l

From these equations we are able to obtain the following by direct

t(x)

computatibn.

V(x) = x + x3 + 3x5 + 10x7 + 39x9 + 160xn + 702x13 + 3177x15 + ...
T(x) = x2 + 2x4 + 7x6 + 26x8 + 107x10 +458x12 + zossx14 + 9498x16 + ...
t(x) = x2 + x4 + 2x6 + 5x8 + 15x10 + 49x12 + 180x14 + 7le16 + ...

If desired, the correctness of the first 5 coefficients of t(x) can
easily be checked firsthand by means of the tree diagrams found in

[9], Appendix 3.

59

Section 3.5
The Edge Independence Number for Sn(G)

For any graph G, the edge independence number B](G) of G is

 

the maximum number of edges among all the l-regular subgraphs of G,
or equivalently, the maximum cardinality of any independent set of __
edges in G. For example, 81(K(m,n)) = min (m,n). The observation néw~1
that a graph G has a l-factor if and only if 81(6) = [GI/2 suggests -
that the parameter 6] can be viewed as a generalization of the l-factor

concept. In general, |Gl/2 is an upper bound for 31(9), but when G j

 

has no l-factor, 81(G) may be much less than this. For example, L“‘b
K(l,p-l) is connected and has arbitrarily large order p, yet
81(K(1.p-1)) =1.
If, for any real number r, we denote by [r] the greatest
integer not exceeding r, then without specializing the graph G under
consideration, the best possible upper bound for 81(G) is [|G|/2].
Letting f(g) denote either of the graph—valued functions T(G) or Gn
(n 3_2), we next show that 81(f(G)) invariably attains this upper

bound, thereby generalizing Corollary 3.9b.

Theorem 3.11. Let G be a connected graph and f(G) denote either one
of the graph-valued functions Gn (n 3_2) or T(G). Then 81(f(G)) =
[lf(G)|/21-

Epggf, Suppose that G is a connected (p,q)-graph and f(G) is either
Gn (n 3_2) or T(G). In the event that |f(G)| is even, the assertion

reduces to Corollary 3.9b. Assume, then, that |f(G)| is odd.

60

For f(G) = Gn (n 3_2), |f(G)| = p, and since G2 is a
subgraph of G", it suffices to show that 81(62) = 9—5—1 = [43-].
Let v be any point in G which is not a cutpoint of G (this is
impossible only if G = K], in which case there is nothing to prove).

Since G-v is connected and (G-v)2 has even order, by Corollary 3.9b,

81((G-v)2) = E—%—l. Since (G-v)2 is a subgraph of G2, 81(G2) = E—%—l- TEEIi

also. ' I
For f(G) = T(G) = 52(G), since S(G) is a connected graph of _

order p+q, 81(T(G)) = 81(52(G)) = [E—g—H] = [AI%?11] follows from the : j

 

result shown in the preceding paragraph. i-ww

Corollary 3.11. Let G be a graph having components C1, C2, ..., Ck,

 

and let f(G) denote either one of the Tr2ph57alued functions Gn
k f C.
(n a 2) or T(G). Then 31mm) = Z ———2-‘—.
i=1
As regards the nth subdivision graph S11(G), Theorem 3.7 and

Lemma 3.1 generalize to the following.

Theorem 3.12. Let G be a connected graph and k any positive integer.

Then,
(1) 81(82k(G)) = [|52k(G)|/2] if and only if 81(G) = [|G|/2], and
(2) 81(52k_](G)) = 1152k_,(e)1/21 if and oniy ii 81(S(G)) = [|s1e)|/21.

Proof. Let G be a connected (p,q)-graph, so that |S(G)| = p + q,
ISZk-l(G)| = p + (2k - l)q, and |52k(G)| = p + 2kq. Each of the

graphs 51(6), 1 = 1, 2k - l, or 2k, is a union of q disjoint v1-vj

61

paths P11 where each path P11 corresponds to the edge Vivj in G and
V = {v1, v2, ..., vp} is the set of points in S1(G) corresponding to
the points of G.

For part (1). When p is even, (1) is a restatement of

 

Theorem 3.7; we therefore assume that p is odd. For the sufficiency
portion of (l), we assume B](G) = (p - 1)/2 and seek to prove that
81(52k(G)) = (p + 2kq - l)/2. Let F be a set of (p - l)/2 independent
edges in G. Each of the (p - l)/2 v1-vj paths of length 2k + l in
$2k(G) corresponding to edges of F yield k + 1 independent edges;
denote the set of these (p - l)(k + l)/2 independent edges by F'.
Each of the remaining q - (p - l)/2 v1-vj paths yield k additional
independent edges which are mutually nonadjacent with the edges in F',
so that altogether $2k(G) contains (p — l)(k + l)/2 + (q - (p - l)/2)k
= (p + 2kq - l)/2 independent edges.

Conversely, if 81(52k(G)) = (p + 2kq - l)/2, to show that
81(6) = (p - l)/2, assume to the contrary that 81(6) §_(p - 3)/2.
Then no more than (p - 3)/2 of the v1-vj paths of length 2k + 1 in
$2k(G) can fail to share a common point (otherwise the edges in G
corresponding to these paths form a set of independent edges with
cardinality greater than (p - 3)/2) and each such path yields at
most k + 1 independent edges; denote the set of all such independent
edges from these paths by F'. Each of the remaining v1-vj paths of
length 2k + 1 contains at least one point common to an edge of F',
so that each such path yields at most k additional independent edges

which are mutually nonadjacent with the edges in F'. Thus the

62

number of independent edges in $2k(G) is no more than (p - 3)(k + l)/2
+ (q - (p - 3)/2)k = (p + 2kq - 3)/2, a contradiction. Hence
81(6) = (p -1)/2.

For part (2). When p + q is even, (2) becomes Lemma 3.1; we
therefore assume p + q is odd (so that p + (2k - l)q is also odd).
Supposing that 81(S(G)) = (p + q - l)/2, we must check that
81(52k-l(6)) = (p + (2k - l)q - l)/2. All edges in S(G) have the
form ”ivj’ where vjEV and u1. GEV, so that for any set F of
(p + q - l)/2 independent edges in S(G), every point of S(G), except
one, belongs to an edge in F. Furthermore, the edges of F determine
(p + q - l)/2 v1-vj paths P15 of length 2 in S(G), each of which con-
tributes one edge to F, and q - (p + q - l)/2 other vk-v1 paths Pkl’
each of which contains no edge of F; thus the points vk and v1 of
such paths Pkl must belong to edges in F (otherwise S(G) contains more
than (p + q - l)/2 independent edges). Consequently, in SZk-l(G)
each path of length 2k corresponding to some Pij yields k independent
edges and each path of length 2k corresponding to some Pkl yields
(k - 1) additional independent edges, so that altogether we have a
set of k(p + q - l)/2 + (k - l)(q - (p + q - l)/2) = l/2(p + (2k - l)q - 1)
independent edges.

The necessity portion of (2) follows immediately by taking k = 1.
This completes the proof of Theorem 3.12.

Theorem 3.12(2) is illustrated in Figure 3.5 with a graph G
having order 6 and 7 edges for which 81(S(G)) = [13/2] = 6 and
31(s3(s)) = [1/2(5 + 3(7))1 = [27/2] = 13 (the edges in the independent

63

'0 3 3

(5 5(6) 53(6)
Figure 3.5. A (6,7)-graph G along with S(G) and 53(3)-

sets of maximum cardinality are darkened). Figure 3.5 also
illustrates another result that applies to Sn(G), for an an odd

integer, which we state next.

Theorem 3.13. Let G be a connected (p,q)-graph. Then

 

kq if G is a tree.

81(52k'](6)) = kq + p - q otherwise.
Egggf, If the connected (p,q)-graph G is a tree, then we shall
prove that 81(52k-1(G)) = kq by showing that for every tree with p
points, a maximal independent set F of edges in 52k-1(G) has cardinality
kq and that for any endpoint w in SZk-T(G)’ the edges u1v1, for
l §_i §_kq, of F may be selected so that d(w,u1) is odd and d(w,v1) =
d(w,u1) + 1. We proceed using induction on the order p of G.

The assertion is immediate for trees of order 1 or 2.

Now assume the assertion holds for trees on fewer than p

points and consider a tree G with order p. For any endpoint v of G,

 

64

let G' denote the tree on p - 1 points obtained from G by deleting
v and its incident edge uv; by the induction assumption, an
independent set F' of maximum cardinality of edges in $2k_](G') has
k(p - 2) members u1v1, for l g-i §;k(p - 2), which can be chosen in
such a way that for any endpoint w in $2k_](G') which is distinct
from u, d(w,u1) is odd and d(w, v1) = d(w,u1) + 1. Since 52k-1(G)
can be regarded as formed from 52k-](G') by the addition of a u-v
path P of even length 2k, it follows that the desired largest
independent set F of edges for 52k-l(G) results by annexing the k
alternate edges of P, beginning with the edge incident with v, to F'.

Next we consider connected graphs which contain at least one
cycle. Proceeding by induction on the number of edges q, we shall
prove that for any such (p,q)-graph G, each largest independent set
F of edges of 52k-1(G) has cardinality p + (k - l)q and contains an
edge incident with each point of 52k-1(G) which corresponds to a
point in G. In particular, we have that B](S2k_](G)) = kq + p - q.

If G is unicyclic (so that p = q), then Theorem 3.8 shows
that 52k-1(G) has a l-factor F, hence F is a largest independent set
of edges of cardinality l/2|52k_](G)| = 1/2(p + (2k - l)q) = kq =
kq+p-q.

The induction begins with q = 3; the only appropriate graph
having 3 edges is K3, a unicyclic graph, which therefore satisfies
the induction assumption.

So now let G be a connected (p,q)-graph with two or more

cycles and let 6' denote the connected 03,q-l)-graph obtained from

65

G by deleting an edge uv not belonging to every cycle in G. Then

G' contains at least one cycle and, by the induction assumption,
every independent set F' of k(q - l) + p - (q - l) edges in $2k_1(G')
contains an edge incident with each point of 52k_](G') corresponding
to a point in G'. Since 52k-1(G) differs from $2k_](G') only by the
presence of a u-v path P of length 2k and both u and v are incident
with members of F', then an independent set of F edges with maximum
cardinality for 52k-1(G) is obtained by adding to some set F' any
collection of k - 1 mutually nonadjacent edges from P, none of which
is incident with either u or v. Then |F| = k(q - l) + p - (q - l)

+ (k - l) = kq + p - q and, moreover, every point of SZk-l(G) cor-
responding to a point in G is incident with an element of F.

This completes the proof of Theorem 3.13.

In the case of a connected (p,q)-graph G. Theorem 3.8 is a
corollary to Theorem 3.13. For if the graph 52k-1(G) has a l-factor,
then since its order is p + (2k - l)q, we have l/2(p + (2k - l)q) =
81(6) = kq + p - q (G is not a tree since that would imply that
p + (2k - l)q is odd). Simplifying, we obtain p = q, which means
that G is unicyclic. Conversely, if G is unicyclic, then
81(SZk-1(G)) = kq + p - q. But since p = q, this value is equal to

l/2|52k_](G)|, implying that S G) has a l-factor.

2k-l(
By combining Theorem 3.13, Theorem 3.7, and the well known

facts that the complete graph Kp has a l-factor if and only if p is

even and that the complete bipartite graph K(r,s) has a l-factor if

and only if r = s, we obtain the following corollaries.

 

66

Corollary 3.13a. Sn(Kp) has a l-factor if and only if either p = 3

and n is odd or both n and p are even.

Corollary 3.13b. Sn(K(r,s)) has a l-factor if and only if either

r = s = 2 and n is odd or r = s and n is even.

The analogous result to Theorem 3.13 for 81(Sn(G))s with n
an even integer, is simpler to state but somewhat more difficult to

apply, as the value of 81(6) is required.

 

Theorem 3.14. Let G be a connected (p,q)-graph. Then 81(52k(G)) =
kq + 81(6). '

Proof. Suppose that F0 is any independent set of edges of G having
cardinality |F0| = 31(6) = r. Let both the points of G and the points
of $2k(G) corresponding to the points of G be labeled as v1, v2, ...,

vp; to each edge Vivj in G, denote the corresponding v1-vj path of

length 2k + l in $2k(G) by Pij' From each Pij

Vivj in F0, we select the available k + l mutually nonadjacent edges;

corresponding to an edge

from each P11 corresponding to an edge Vivj not in F0, we select the

k mutually nonadjacent edges, none of which is incident with v1 or

vj. Clearly this selection is always possible. Let F1 denote this
collection of r(k + l) + (q - r)k = kq + r independent edges in $2k(G).
All that remains is to verify that F1 is an independent set of edges

in $2k(G) having maximum cardinality.

For any independent set F2 of edges in $2k(G) with maximum

cardinality |F2| 3.|F1|, we obtain another independent set of edges

 

67

F3 from F2 having the same cardinality in the following way. The
edges of F2 are distributed among the q paths P11 of $2k(G), some
of these paths--say s in number--containing k + l of these edges
each, while the other q-s paths each contain only k edges of F2.
Whenever a vivj path P1j contains exactly k edges of F2, at least
one of v1 and vj must be incident with an edge of F2 not in P11,
since otherwise k + 1 edges could be used in F2 for that path P11,
contradicting the maximality of |F2|. Replacing this set of k edges
by the set of k mutually nonadjacent edges of P11, no member of which
is incident with v1 or vj (if this latter set is distinct from the
former) yields a maximal independent set of edges having the same
cardinality as F2. Repeating this process for every path P11 con-
taining only k edges of F2, we obtain the promised independent set

F3 where |F3| = IFZI. Now choose a new independent set of edges in

G consisting of the edges Vivj corresponding to the s v1-vj paths

Pij containing k + l edges of F3. Since |F3| = s(k + l) + (q - s)k
3_r(k + 1) + (q - r)k = |F1| implies s 3_r, and since FO has maximum
cardinality, we have s = r. Therefore, the cardinality of F1 is
equal to that of F3, and hence to |F2| as well. Thus F1 is a largest

independent set of edges in S2k(G).

For connected (p,q)-graphs, Theorem 3.7 follows directly from
Theorem 3.14. For if G has a l-factor (so that 81(6) = p/2), then
81(S2k(G)) = kq + p/2 = l/2|SZk(G)| implies that $2k(G) has a
l-factor. Conversely, if $2k(G) has a l-factor, then 81(52k(6)) =

 

68

l/2|52k(G)| = kq + p/2 = kq + 81(G) implies that 81(G) = p/2, so that
G also has a l-factor.

Another application of Theorem 3.14 is obtained by setting
G = Kp or G = K(r,s). This procedure yields well known necessary and
sufficient conditions that G have a l-factor, as noted in the remarks
preceding Corollary 3.13a.

The formulas presented in Theorems 3.13 and 3.14 are suffi-
ciently similar so that one is tempted to try to combine them. One

such formulation is the following.

Corollary 3.14. Let G be a connected (p,q)-graph. Then.

 

!
{gig + 12[(-l)n + l]B](G), if G is a tree,
81(5n(G)) =1

 

 

 

qu+0'14VNp-n+<‘+gUDamhomema,

where curly brackets denote the greatest integer function.

10.

ll.

12.

13.

BIBLIOGRAPHY

Mehdi Behzad. Graphs and Their Chromatic Numbers. Ph.D. Thesis,
Michigan State University (1965).

 

Mehdi Behzad and Gary Chartrand. An Introduction to the Theory
of Graphs, Allyn and Bacon, Inc., 1972.

 

Gary Chartrand. "0n Hamiltonian Line Graphs.‘I Transactions of
the American Mathematical Society 3 (1968), 559-566.

 

 

Gary Chartrand; Dennis Geller; Stephen Hedetniemi. "Graphs with
Forbidden Subgraphs." Journal of Combinatorial Theory 1 (1971),
12-41.

 

Gary Chartrand and Frank Harary. "Planar Permutation Graphs."
Les Annales de l'Institut Henri Poincare (Section B), 3 (1967),
433-438.

Gary Chartrand; A. M. Hobbs; C. St. J. A. Nash-Williams; S. F.
Kapoor. "The Square of a Block Is Hamiltonian Connected."
(To appear.)

Gary Chartrand and H. V. Kronk. "Randomly Traceable Graphs."
SIAM Journal of Applied Mathematics 4 (1968), 696-700.

 

H. Fleischner. "The Square of Every Non-separable Graph Is
Hamiltonian Connected." (To appear.)

Frank Harary. Graph Theory. Addison-Wesley Co., 1969.

 

Frank Harary and C. St. J. A. Nash-Williams. "On Eulerian and
Hamiltonian Graphs and Line Graphs." Canadian Mathematical
Bulletin 8 (1965), 701-709.

 

F. Harary and E. M. Palmer. Graphical Enumeration. Academic
Press, New York, 1973. (To appear.)

 

H. A. Jung. "Zu Einem Isomorphiesatz von Whitney ffir Graphen."
Math. Ann. 164 (1966), 270-271.

0. Ore. "A Problem Regarding the Tracing of Graphs." Elem.
Math. 6 (1951), 49-53.

69

F

14.

15.

16.

17.

70

R. Otter. "The Number of Trees." Ann. of Math. 49 (1948),
583-599.

Wayne S. Petroelje and Curtiss E. Wall. "Graph-Valued Functions
and Hamiltonian Graphs.“ Recent Trends in Graph Theory (M.
Capobianco, J. B. Frechen, and M. Krolik, editors). Springer-
Verlag, Berlin (1971), 211-213.

 

G. Polya. "Kombinatorische Anzahlbestimmungen ffir Gruppen,
Graphen und Chemische Verbindungen.“ Acta. Math. 68 (1937),
145-254.

 

M. James Stewart. "A Topological Influence: Homeomorphically
Irreducible Graphs." The Many Facets of Graph Theory (G. Char-
trand and S. F. Kapoor, editors). Springer-Verlag, Berlin
(1969), 281-282.

 

   

M1111111111111111111111111111111ES