Corona

Corona — корона.

1. The corona [math]\displaystyle{ \,coro(G) }[/math] of a graph [math]\displaystyle{ \,G }[/math] is a graph obtained from [math]\displaystyle{ \,G }[/math] by adding a pendant edge to each vertex of [math]\displaystyle{ \,G }[/math]. See also Crown of graphs.

2. Let [math]\displaystyle{ \,\Omega(G) }[/math] denote the family of all maximum stable sets of the graph [math]\displaystyle{ \,G }[/math]. We define [math]\displaystyle{ \,corona(G) = \cup\{S: \; S \in \Omega(G)\} }[/math] as the set of vertices belonging to some maximum stable sets of [math]\displaystyle{ \,G }[/math].

3. [math]\displaystyle{ \,G \circ H }[/math] is called the corona of graphs, if it is obtained from the disjoint union of [math]\displaystyle{ \,G }[/math] and [math]\displaystyle{ \,n }[/math] copies of [math]\displaystyle{ \,H }[/math] (where [math]\displaystyle{ \,n = |V(G)| }[/math]) by joining a vertex [math]\displaystyle{ \,x_{i} }[/math] of [math]\displaystyle{ \,G }[/math] with every vertex from [math]\displaystyle{ \,i }[/math]-th copy of [math]\displaystyle{ \,H }[/math], for each [math]\displaystyle{ \,i = 1, 2, \ldots, n }[/math].

Let [math]\displaystyle{ \,k }[/math] be a fixed integer, [math]\displaystyle{ \,k \geq 1 }[/math], [math]\displaystyle{ \,k }[/math]-corona [math]\displaystyle{ \,kG \circ H }[/math] is a graph obtained from [math]\displaystyle{ \,k }[/math] copies of [math]\displaystyle{ \,G }[/math] and [math]\displaystyle{ \,|V(G)| }[/math] copies of [math]\displaystyle{ \,H }[/math] with appropriate edges between each vertex [math]\displaystyle{ \,x^{j}_{i} }[/math] of the copy [math]\displaystyle{ \,G^{j} }[/math] and all vertices of the copy of [math]\displaystyle{ \,H_{i} }[/math].

The [math]\displaystyle{ \,2 }[/math]-corona of a graph [math]\displaystyle{ \,H }[/math] is a graph of order [math]\displaystyle{ \,3|V(H)| }[/math] obtained from [math]\displaystyle{ \,H }[/math] by attaching a path of length [math]\displaystyle{ \,2 }[/math] to each vertex so that the attached paths are vertex disjoint.

Литература

• Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.