Graph and digraph embedding problems.
Loading...
Date
1996
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
This thesis is a study of the symmetry of graphs and digraphs by considering certain
homogeneous embedding requirements.
Chapter 1 is an introduction to the chapters that follow. In Chapter 2 we present
a brief survey of the main results and some new results in framing number theory.
In Chapter 3, the notions of frames and framing numbers is adapted to digraphs. A
digraph D is homogeneously embedded in a digraph H if for each vertex x of D and
each vertex y of H, there exists an embedding of D in H as an induced subdigraph
with x at y. A digraph F of minimum order in which D can be homogeneously
embedded is called a frame of D and the order of F is called the framing number of
D. We show that that every digraph has at least one frame and, consequently, that
the framing number of a digraph is a well defined concept. Several results involving
the framing number of graphs and digraphs then follow. Analogous problems to those
considered for graphs are considered for digraphs.
In Chapter 4, the notions of edge frames and edge framing numbers are studied.
A nonempty graph G is said to be edge homogeneously embedded in a graph H if for
each edge e of G and each edge f of H, there is an edge isomorphism between G and
a vertex induced subgraph of H which sends e to f. A graph F of minimum size
in which G can be edge homogeneously embedded is called an edge frame of G and
the size of F is called the edge framing number efr(G) of G. We also say that G is
edge framed by F. Several results involving edge frames and edge framing numbers
of graphs are presented.
For graphs G1 and G2 , the framing number fr(G1 , G2 ) (edge framing number
ef r(GI, G2 )) of G1 and G2 is defined as the minimum order (size, respectively) of a
graph F such that Gj (i = 1,2) can be homogeneously embedded in F. In Chapter 5
we study edge framing numbers and framing number for pairs of cycles. We also
investigate the framing number of pairs of directed cycles.
Description
Thesis (Ph.D.)-University of Natal, Pietermaritzburg, 1996.
Keywords
Graph theory., Theses--Mathematics.