The MATCHING DOMINATION IN GRAPHS

Abstract

A dominating set D is called a connected dominating set, if it induces a connected subgraph in G. Since a dominating set must contain atleast one vertex from every component of G, it follows that a connected dominating set for a graph G exists if and only if G is connected. The minimum of cardinalities of the connected dominating sets of G is called the connected domination number of G and is denoted by (G). We have defined new parameter called the matching dominating set and the matching domination number. We prove the following:

•  If G is a graph without isolated vertices, then γ ≤ . y_m.
• _{There exist bipartite graphs for which .y}