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

'''Corona''' — ''[[корона]].''

'''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

''[[Crown of graphs]]''.

'''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

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

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>.

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>.

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.

 

 

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