Edge frames of graphs: A graph embedding problem (Q1377875)

A graph \(G\) is edge homogeneously embedded in a graph \(H\) if for every edge \(e\) of \(G\) and each edge \(f\) of \(H\), there exists 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 \(\text{efr} (G)\) of \(G\). The author establishes a number of results on the edge framing number of a graph which include the following: It is shown that every graph has at least one edge frame and consequently, that the edge framing number of a graph is well defined. The author establishes a number of bounds on \(\text{efr} (G)\) for a given graph \(G\) as well as some properties of an edge frame of \(G\). The author also defines the edge framing ratio \(\text{efrr} (G)\) as the ratio \(\text{efr} (G)/ |E(G)|\) and establishes bounds for this ratio and shows that if \(r\) is a rational number in the interval \([1,3)\) then there exists a graph \(G\) with \(\text{efrr} (G)=r\). To conclude the paper the author finds the edge framing number of some pairs of graphs where one member of the pair is a star and the other member a cycle.