Framing number

Framing number --- фреймовое число.

A graph [math]\displaystyle{ G }[/math] is homogeneously embedded in a graph [math]\displaystyle{ H }[/math] if for every vertex [math]\displaystyle{ x }[/math] of [math]\displaystyle{ G }[/math] and every vertex [math]\displaystyle{ y }[/math] of [math]\displaystyle{ H }[/math] there exists an embedding of [math]\displaystyle{ G }[/math] in [math]\displaystyle{ H }[/math] as an induced subgraph with [math]\displaystyle{ x }[/math] at [math]\displaystyle{ y }[/math]. A graph [math]\displaystyle{ F }[/math] of minimum order in which [math]\displaystyle{ G }[/math] can be homogeneously embedded is called a frame of [math]\displaystyle{ G }[/math], and the order of [math]\displaystyle{ F }[/math] is called the framing number [math]\displaystyle{ fr(G) }[/math] of [math]\displaystyle{ G }[/math].

For graphs [math]\displaystyle{ G_{1} }[/math] and [math]\displaystyle{ G_{2} }[/math], the framing number [math]\displaystyle{ fr(G_{1},G_{2}) }[/math] is defined as the minimum order of a graph [math]\displaystyle{ F }[/math] such that [math]\displaystyle{ G_{i} }[/math] ([math]\displaystyle{ i=1,2 }[/math]) can be homogeneously embedded in [math]\displaystyle{ F }[/math]. The graph [math]\displaystyle{ F }[/math] is called a frame of [math]\displaystyle{ G_{1} }[/math] and [math]\displaystyle{ G_{2} }[/math]. Frames and framing numbers for digraphs were defined similarly.