Independent set dominating sets in bipartite graphs

Bohdan Zelinka

Abstract. The paper continues the study of independent set dominating sets in graphs which was started by E. Sampathkumar. A subset \(D\) of the vertex set \(V(G)\) of a graph \(G\) is called a set dominating set (shortly sd-set) in \(G\), if for each set \(X \subseteq V(G)-D\) there exists a set \(Y \subseteq D\) such that the subgraph \(\langle X \cup Y\rangle\) of \(G\) induced by \(X \cup Y\) is connected. The minimum number of vertices of an sd-set in \(G\) is called the set domination number \(\gamma_s(G)\) of \(G\). An sd-set \(D\) in \(G\) such that \(|D|=\gamma_s(G)\) is called a \(\gamma_s\)-set in \(G\). In this paper we study sd-sets in bipartite graphs which are simultaneously independent. We apply the theory of hypergraphs.

Keywords: set dominating set, set domination number, independent set, bipartite graph, multihypergraph.

Mathematics Subject Classification: 05C69, 05C65.

Full text (pdf)