Return to search
## Graph and digraph embedding problems.

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. / Thesis (Ph.D.)-University of Natal, Pietermaritzburg, 1996.

Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:ukzn/oai:http://researchspace.ukzn.ac.za:10413/5928 |

Date | January 1996 |

Creators | Maharaj, Hiren. |

Contributors | Henning, Michael A. |

Source Sets | South African National ETD Portal |

Language | English |

Detected Language | English |

Type | Thesis |

Page generated in 0.0017 seconds