Corona: различия между версиями
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…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Corona''' | '''Corona''' — ''[[корона]].'' | ||
'''1.''' The '''corona''' <math>coro(G)</math> of a graph <math>G</math> is a graph obtained from | '''1.''' The '''corona''' <math>\,coro(G)</math> of a [[graph, undirected graph, nonoriented graph|graph]] <math>\,G</math> is a graph obtained from <math>\,G</math> by adding a ''[[pendant edge]]'' to each [[vertex]] of <math>\,G</math>. See also | ||
<math>G</math> by adding a ''pendant edge'' to each vertex of <math>G</math>. See also | ''[[Crown of graphs]]''. | ||
''Crown of graphs''. | |||
'''2.''' Let <math>\Omega(G)</math> denote the family of all maximum stable sets of the | '''2.''' Let <math>\,\Omega(G)</math> denote the family of all maximum stable sets of the | ||
graph <math>G</math>. We define <math>corona(G) = \cup\{S: \; S \in \Omega(G)\}</math> as the | graph <math>\,G</math>. We define <math>\,corona(G) = \cup\{S: \; S \in \Omega(G)\}</math> as the | ||
set of vertices belonging to some maximum stable sets of <math>G</math>. | set of vertices belonging to some maximum stable sets of <math>\,G</math>. | ||
'''3.''' <math>G \circ H</math> is called the '''corona''' of graphs, if it is obtained | '''3.''' <math>\,G \circ H</math> is called the '''corona''' of graphs, if it is obtained | ||
from the disjoint union of <math>G</math> and <math>n</math> copies of <math>H</math> (where <math>n = | from the disjoint union of <math>\,G</math> and <math>\,n</math> copies of <math>\,H</math> (where <math>\,n = |V(G)|</math>) by joining a vertex <math>\,x_{i}</math> of <math>\,G</math> with every vertex from <math>\,i</math>-th copy of <math>\,H</math>, for each <math>\,i = 1, 2, \ldots, n</math>. | ||
|V(G)|</math>) by joining a vertex <math>x_{i}</math> of <math>G</math> with every vertex from | |||
<math>i</math>-th copy of <math>H</math>, for each <math>i = 1, 2, \ldots, n</math>. | |||
Let <math>k</math> be a fixed integer, <math>k \geq 1</math>, '''<math>k</math>-corona''' <math>kG \circ H</math> | Let <math>\,k</math> be a fixed integer, <math>\,k \geq 1</math>, '''<math>\,k</math>-corona''' <math>\,kG \circ H</math> is a graph obtained from <math>\,k</math> copies of <math>\,G</math> and <math>\,|V(G)|</math> copies of <math>\,H</math> with appropriate [[edge|edges]] between each vertex <math>\,x^{j}_{i}</math> of the copy <math>\,G^{j}</math> and all vertices of the copy of <math>\,H_{i}</math>. | ||
is a graph obtained from <math>k</math> copies of <math>G</math> and <math>|V(G)|</math> copies of <math>H</math> | |||
with appropriate edges between each vertex <math>x^{j}_{i}</math> of the copy | |||
<math>G^{j}</math> and all vertices of the copy of <math>H_{i}</math>. | |||
The '''2-corona''' of a graph <math>H</math> is a graph of order <math>3|V(H)|</math> | The '''<math>\,2</math>-corona''' of a graph <math>\,H</math> is a graph of order <math>\,3|V(H)|</math> obtained from <math>\,H</math> by attaching a [[path]] of length <math>\,2</math> to each vertex so that the attached paths are vertex disjoint. | ||
obtained from <math>H</math> by attaching a path of length 2 to each vertex so | |||
that the attached paths are vertex disjoint. | ==Литература== | ||
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | |||
Текущая версия от 12:21, 16 февраля 2017
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.