Аноним

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.