Graph and digraph embedding problems.

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.