Opuscula Math. 25, no. 2 (2005), 345-349

Opuscula Mathematica

Independent set dominating sets in bipartite graphs

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)