Point-set domatic numbers of graphs. (English) Zbl 0933.05112

Zelinka, Bohdan

Math. Bohem. 124, No. 1, 77-82 (1999).

Summary: A subset \(D\) of the vertex set \(V(G)\) of a graph \(G\) is called point-set dominating, if for each subset \(S\) of \(V(G)-D\) there exists a vertex \(v\in D\) such that the subgraph of \(G\) induced by \(S\cup \{v\}\) is connected. The maximum number of classes of a partition of \(V(G)\), all of whose classes are point-set dominating sets, is the point-set domatic number \(d_p(G)\) of \(G\). Its basic properties are studied in the paper.

MSC:

05C69

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Keywords:

dominating set; point-set dominating set; point-set domatic number; bipartite graph