Some general aspects of the framing number of a graph

Wayne Goddard, Michael A. Henning, Ortrud R. Oellermann, Henda C. Swart

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)

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 languageEnglish
Pages (from-to)289-300
Number of pages12
JournalQuaestiones Mathematicae
Volume16
Issue number3
DOIs
Publication statusPublished - Jul 1993
Externally publishedYes

ASJC Scopus subject areas

  • Mathematics (miscellaneous)

Fingerprint

Dive into the research topics of 'Some general aspects of the framing number of a graph'. Together they form a unique fingerprint.

Cite this