Domination in Kneser graphs. (English) Zbl 0778.05043

Ivanćo, Jaroslav; Zelinka, Bohdan

Math. Bohem. 118, No. 2, 147-152 (1993).

A set \(D\) of a graph \(G\) is called dominating if for any \(x\in V(G)-D\) there is a \(y\in D\) adjacent to \(x\). The minimum number of vertices in a dominating set is called the domination number. The domatic number of \(G\) is the maximum number of classes in a partition into dominating sets. In the paper the domination and domatic numbers of a Kneser graph \(K(n,2)\) are determined.

Reviewer: P.Horák (Bratislava)

MSC:

05C35

Extremal problems in graph theory

Keywords:

dominating set; domination number; Kneser graph