Corona

Материал из WikiGrapp
Версия от 14:17, 15 марта 2011; Glk (обсуждение | вклад) (Новая страница: «'''Corona''' --- корона. '''1.''' The '''corona''' <math>coro(G)</math> of a graph <math>G</math> is a graph obtained from <math>G</math> by adding a ''penda…»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

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 2-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 2 to each vertex so that the attached paths are vertex disjoint.