SOME GENERAL-ASPECTS OF THE FRAMING NUMBER OF A DIGRAPH

A digraph D is homogeneously embedded in a diagraph H if for each vert ex 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 o rder of F is called the framing number of D. Several general results i nvolving frames and framing numbers of digraphs are established. The f raming number is determined for a number of classes of digraphs, inclu ding a class of digraphs whose underlying graph is a complete bipartit e graph, a class of digraphs whose underlying graph is C-n + K-1, and the lexicographic product of a transitive tournament and a vertex tran sitive digraph. A relationship between the diameters of the underlying graphs of a digraph and its frame is determined. We show that every t ournament has a frame which is also a tournament. (C) 1998 Elsevier Sc ience B.V. All rights reserved.