Abstract
A graph G is homogeneously embedded in a graph H if for every vertex x of G and every vertex y of H, there exists an embedding of G in H as an induced subgraph with x at y. A graph F of minimum order in which G can be homogeneously embedded is called a frame of G, and the order of F is called the framing number fr(G) of G. The concept of framing numbers may be extended to more than one graph. For n ≥ 2, we prove that fr(K1, 2, Kn) = fr([Kbar]2, Kn) = fr(Kn+1—e) and we establish the value of these framing numbers. The framing number of the wheel Wn+1 = Cn + K1 is determined for all n ≥ 3. The framing ratio of a graph G is the ratio fr(G)/p(G), where p(G) is the number of vertices of G. The existence of a class of graphs whose framing ratios are at least 2 is established. The relationship between the diameter of a frame F of a graph G and the radius and diameter of G is also investigated, and it is conjectured that rad G ≤ diam F ≤ diam G. 1991 Mathematics Subject Classifkation. 05C99.
Original language | English |
---|---|
Pages (from-to) | 289-300 |
Number of pages | 12 |
Journal | Quaestiones Mathematicae |
Volume | 16 |
Issue number | 3 |
DOIs | |
Publication status | Published - Jul 1993 |
Externally published | Yes |
ASJC Scopus subject areas
- Mathematics (miscellaneous)