On perfect and unique maximum independent sets in graphs

Title:

On perfect and unique maximum independent sets in graphs

Creator:

Volkmann, Lutz

Identifier:

https://cdk.lib.cas.cz/client/handle/uuid:46f05bd2-6ac2-47b0-9fd4-1e926cf53f90
uuid:46f05bd2-6ac2-47b0-9fd4-1e926cf53f90
doi:10.21136/MB.2004.134148

Subject:

independent sets, perfect independent sets, unique independent sets, strong unique independent sets, and super unique independent sets

Type:

model:article and TEXT

Format:

bez média and svazek

Description:

A perfect independent set I of a graph G is defined to be an independent set with the property that any vertex not in I has at least two neighbors in I. For a nonnegative integer k, a subset I of the vertex set V (G) of a graph G is said to be k-independent, if I is independent and every independent subset I' of G with |I' | ≥ |I| − (k − 1) is a subset of I. A set I of vertices of G is a super k-independent set of G if I is k-independent in the graph G[I, V (G) − I], where G[I, V (G) − I] is the bipartite graph obtained from G by deleting all edges which are not incident with vertices of I. It is easy to see that a set I is 0-independent if and only if it is a maximum independent set and 1-independent if and only if it is a unique maximum independent set of G. In this paper we mainly investigate connections between perfect independent sets and k-independent as well as super k-independent sets for k = 0 and k = 1.

Language:

English

Rights:

http://creativecommons.org/publicdomain/mark/1.0/
policy:public

Coverage:

273-282

Source:

Mathematica bohemica | 2004 Volume:129 | Number:3

Harvested from:

CDK

Metadata only:

false