Goddard, Wayne; Henning, Michael A.; Oellermann, Ortrud R.; Swart, Henda C. Some general aspects of the framing number of a graph. (English) Zbl 0794.05123 Quaest. Math. 16, No. 3, 289-300 (1993). Let \(G= G(V,E)\), \(| V|= p(G)\), be a finite undirected 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\). Such a graph \(H\) of minimum order is called a frame of \(C\) and denoted by \(F\), its order is called the framing number \(\text{fr}(G)\) of \(G\). This concept has been extended to more than one graph by Chartrand, Gavlas and Schultz: The framing number \(\text{fr}(G_ 1,G_ 2)\) of \(G_ 1\) and \(G_ 2\) is the minimum order of a graph \(F\) such that \(G_ 1\) and \(G_ 2\) can be homogeneously embedded in \(F\). In another paper these authors found conditions for the existence of such graphs \(H\) of order \(n\) in which \(G\) resp. \(G_ 1\) and \(G_ 2\) can be homogeneously embedded. Further the ratio \(\text{frr}(G)={\text{fr}(G)\over p(G)}\) is called the framing ratio of \(G\).In the present paper the authors obtain the following results: (1) For \(n\geq 2\), \(\text{fr}(K_{1,2},K_ n)=\text{fr}(\overline K_ 2,K_ n)= \text{fr}(K_{n+1}- e)= p(n,2)\), where therefore \(p(n,2)\) is the minimum order of a graph such that every vertex is in a \(K_ n\) and in a \(\overline K_ 2\) (Theorem 1). For \(p(2,2)= 4\), \(p(3,2)= 6\) and for \(n\geq 4\) the following is proved: (a) If \(m\geq 2\) and \(0\leq i\leq m-1\), then \(p(m^ 2+ 1-i,2)=(m+ 1)^ 2- i\). (b) If \(m\geq 2\) and \(1\leq i\leq m\), then \(p(m^ 2+1+i,2)= (m+1)^ 2+1+i\).(2) Determination of \(\text{fr}(W_{n+1})\) of the wheel \(W_{n+1}= C_ n+ K_ 1\), \(n\geq 3\). It holds \(\text{fr}(W_ 4)= 4\) and \(\text{fr}(W_ 5)= 6\). By Theorem 2 we have \(\text{fr}(W_{n+1})=2n\) for all integers \(n\geq 5\).(3) It is known that for every rational number \(r\in [1,2)\), there exists a graph \(G\) with \(\text{frr}(C)= r\). In the present paper the class of brooms is investigated, where a star \(K_{1,n-2}\) with one edge subdivided once is said to be a broom \(B_ n\), \(n\geq 5\). It holds \(\text{fr}(B_ 5)= 8\) and \(\text{fr}(B_ 6)= 11\), and for \(n\geq 7\) is proved that \(\text{fr}(B_ n)\geq 2n\) (Theorem 3). For integers \(n\geq 7\) this means that \(\text{frr}(B_ n)\) is at least 2.(4) If \(G\) is a connected graph with diameter \(d\) and \(F\) is a frame of \(G\), then \(\text{diam }F\leq d+1\) (Theorem 4). This result shows that the diameter of a frame of a connected graph cannot be too large.The authors conjecture: If \(F\) is a frame of a connected graph \(G\), then \(\text{diam }G\geq \text{diam }F\geq\text{rad }G\), where \(\text{rad }G\) means the radius of \(G\). Reviewer: H.-J.Presia (Ilmenau) Cited in 1 ReviewCited in 3 Documents MSC: 05C99 Graph theory Keywords:embedding; frame; framing number; framing ratio; star; broom PDFBibTeX XMLCite \textit{W. Goddard} et al., Quaest. Math. 16, No. 3, 289--300 (1993; Zbl 0794.05123) Full Text: DOI References: [1] DOI: 10.1002/jgt.3190060404 · Zbl 0499.05032 [2] DOI: 10.1002/jgt.3190080108 · Zbl 0543.05056 [3] Chartrand G., Framed! A graph embedding problem · Zbl 0829.05022 [4] Chartrand G., Which trees are framed by the Petersen graph? [5] Chartrand G., Graphs & Digraphs, Second Edition (1986) [6] Cockayne E. J., Ann. Discrete Math. 17 pp 203– (1983) [7] Cockayne E. J., Caribbean J. Sci. Math. 3 pp 29– (1984) [8] Cockayne E. J., Congress. Numer. 29 pp 281– (1980) [9] Cockayne E. J., Ars Combin. 30 pp 50– (1990) [10] Cockayne E. J., Utilitas Math. 33 pp 195– (1988) [11] Erdös P., K [12] DOI: 10.1111/j.1749-6632.1989.tb16395.x [13] DOI: 10.1080/16073606.1990.9631615 · Zbl 0709.05029 [14] Ore O., Theory of Graphs (1962) · Zbl 0105.35401 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.