Corona: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Новая страница: «'''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…»)
 
Нет описания правки
 
Строка 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.