Corona

Материал из WikiGrapp
Перейти к:навигация, поиск

Coronaкорона.

1. The corona \,coro(G) of a graph \,G is a graph obtained from \,G by adding a pendant edge to each vertex of \,G. See also Crown of graphs.

2. Let \,\Omega(G) denote the family of all maximum stable sets of the graph \,G. We define \,corona(G) = \cup\{S: \; S \in \Omega(G)\} as the set of vertices belonging to some maximum stable sets of \,G.

3. \,G \circ H is called the corona of graphs, if it is obtained from the disjoint union of \,G and \,n copies of \,H (where \,n = |V(G)|) by joining a vertex \,x_{i} of \,G with every vertex from \,i-th copy of \,H, for each \,i = 1, 2, \ldots, n.

Let \,k be a fixed integer, \,k \geq 1, \,k-corona \,kG \circ H is a graph obtained from \,k copies of \,G and \,|V(G)| copies of \,H with appropriate edges between each vertex \,x^{j}_{i} of the copy \,G^{j} and all vertices of the copy of \,H_{i}.

The \,2-corona of a graph \,H is a graph of order \,3|V(H)| obtained from \,H by attaching a path of length \,2 to each vertex so that the attached paths are vertex disjoint.

Литература

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