1. Introduction

In the last five decades graph theory has been an explosive growth due to its interaction with and application in several areas like Physical Sciences, Life Sciences, Engineering, Operation Research etc. The fastest growing area within graph theory is the study of domination, the reason being its many and varied applications in such fields as social sciences, communications networks, algorithmic designs etc. The topic of domination was given formal Mathematical definition by C. Berge in 1958 and O. Ore ^[9] in 1962. Berge called the domination as external stability and domination number of coefficient of external stability. Ore introduced the world domination in his famous book ^[9]. This concept lived in hibernation until 1975 when a paper ^[6] published in 1977. This paper brought to light new ideas and potentiality of being applied in variety of areas. The research in domination theory has been broadly classified in ^{[11, 12]}.

In this paper we present some identities of domination set and independent set of graphs containing vertex-disjoint cycles.

2. Preliminaries and Notations

Let be a simple graph (i.e., undirected, without loops and multi edges). The number of vertices namely the cardinality of V is called the order of G and is denoted by . The number of edges of a graph namely the cardinality of E is called the size of G and is denoted by We write to mean the pair and if we say that and are adjacent and and , and re incident.

The open neighbourhood of the vertex v consists of the set of vertices adjacent to v. That is . The closed neighbourhood of v is . For a set , the open neighbourhood N(S) is defined by and the closed neighbourhood by . A vertex is called “an enclave of S”, if A vertex is called “an isolate of of S”, if

The degree of a point v is denoted by is defined as the number of edges incident with v. That is . The maximum and minimum of the degree of vertices of G are denoted by respectively. If , then G is said to be a regular graph of degree r or simply r-regular.

A walk of length k is an alternative sequence of vertices and edges with, i.e., . If all k edges are distinct in a walk, then it is called a Trial. If all the k+1 vertices are distinct in a walk, then it is called a Path. If and if are distinct in a walk then it is called a cycle. If , then W is said to be a walk of a length

We now explain independent set and dominating set of graphs ^{[11, 12]}.

3. Independent Set and Dominating Set

Counting independent sets in graphs is one of several combinatorial counting problems which have received recent attention. Independent sets were introduced into the communication theory on noisy channels ^[7]. From application point of view, domination problems appear in numerous practical setting, ranging from strategic decision such as locating radar stations or emergency services through computational biology to voting system. Variations of dominations such as multiple domination, even/odd domination, distance domination, directed domination, independent domination and connected domination have found numerous application and significant theoretical interest recently.

Independent set

A sub set is an independent set, if no two vertices of S are adjacent. Moreover, the subset containing only one vertex and the empty set also are independent. The number of all independent sets in G is denoted by . For a graph G on , we put . Independence number of graph G is the maximal cardinality of an independent set of vertices. Following are the examples of independent set:

Dominating Set

A subset is called a dominating set, if every vertices of is adjacent to a member of D. A dominating set of G with minimum cardinality is called a minimum dominating set and the cardinality of a minimum dominating set is called the domination number and denoted by . The upper domination number of a graph G denoted by is defined as the maximum cardinality of a minimum dominating set of G. Following are the examples of dominating set:

Independent Dominating set

A set D of vertices in a graph G is called an independent dominating set of G if D is both an independent and a dominating set of G. This set is also called a Stable set or a Kernel of the graph. Independent dominating sets were introduced into the theory of games by Neumann and Margenstern in 1944 ^[8]. The independent domination number is the cardinality of the smallest independent domination set. Following are the examples of independent dominating set:

4. Main Results

We now present identities of domination set and independent set of graphs containing vertex-disjoint cycles. Also present identities related to domination number, upper domination number, Independence number, independent domination number.

Theorem (4.1). Let G be a graph of order n and containing two vertex-disjoint cycles. A dominating set is a minimal dominating set if and only if (i) if i.e. u is an isolate of D. (ii) a vertex for which

Proof. Let D be a minimal dominating set of a graph G having two vertex-disjoint cycles. Suppose a vertex such that

(4.1)

Suppose for every , , then a vertex such that

(4.2)

Since D is a dominating set, we get

Consider then

Let if

Also by 4.1,

Thus is a dominating set which is contradiction, since D is minimal dominating set. Hence

Conversely, Let D be a dominating set and

Since then is not a dominating set.

Suppose (ii) holds, then for some

Hence is not a dominating set. Thus D is a minimal dominating set.

Theorem (4.2). Let G be a graph of order n and containing two vertex-disjoint cycles. If is a dominating set , then

Proof: Let D be a minimum dominating set of a graph G containing two vertex-disjoint cycles, then

Since D is a dominating set and if , then by theorem 4.2, either u is an isolate of S, i.e., or a vertex for which

Since such that v is adjacent to u, thus is also a dominating set and hence

Theorem (4.3). Let G be a graph of order n and containing two vertex-disjoint cycles, then every maximal independent set is a minimal dominating set of G.

Proof. Let G be a graph containing two vertex-disjoint cycles and D be a maximal dominating set in G, then clearly D is a dominating set.

If we assume is not a minimal dominating set, then a vertex for which is a dominating set. Thus a vertex such that u and v are adjacent, which is contradiction. Hence D is a minimal dominating set of G.

Now we are in a position to state the following theorems without proof because it can be easily proved from the theorems given above.

Theorem (4.4). Let G be a graph of order n containing two vertex-disjoint cycles. Then

(a)

(b) and

(c)

Theorem (4.5). Let G be a graph of order n and containing three vertex-disjoint cycles. A dominating set is a minimal dominating set if and only if (i) if i.e. u is an isolate of D. (ii) a vertex for which

Theorem (4.6). Let G be a graph of order n and containing three vertex-disjoint cycles. If is a dominating set , then

Theorem (4.7). Let G be a graph of order n and containing three vertex-disjoint cycles, then every maximal independent set is a minimal dominating set of G.

Next we state identity related to domination number, independence number of a graph contains three vertex-disjoint cycles.

Theorem (4.8). Let G be a graph of order n and containing three vertex-disjoint cycles. Then

(a)

(b)

and (c)

Theorem (4.9). Let G be a graph of order n and containing four vertex-disjoint cycles. A dominating set is a minimal dominating set if and only if

(i) if i.e. u is an isolate of D.

(ii) a vertex for which

Theorem (4.10). Let G be a graph of order n and containing four vertex-disjoint cycles. If is a dominating set , then

Theorem (4.11). Let G be a graph of order n and containing four vertex-disjoint cycles, then every maximal independent set is a minimal dominating set of G.

Next we state identity related to domination number, independence number of a graph contains four vertex-disjoint cycles.

Theorem (4.12). Let G be a graph of order n and containing four vertex-disjoint cycles, then

(a)

(b) and

(c)

5. Conclusion

In this paper, we have presented some identities of domination set and independent set of graphs containing vertex-disjoint cycles. Also presented some identities related to domination number, upper domination number, Independence number and independent domination number of graphs containing vertex-disjoint cycles. This consideration given here would be interesting to apply to other types of graphs.

Acknowledgement

We would like to thank the anonymous referees for numerous helpful suggestions.

References

[1]	A. S. Pedersen, P. D. Vestergaard: Bonds on the number of vertex independent vertex sets in a graph. Taiwanese J. Math., Vol. 10 (6), 2006, 1575-1587.
	In article
[2]	A. S. Pedersen, P. D. Vestergaard: The number of independent sets in unicyclic graphs, Discrete Appl. Math., Vol. 152 (1-3), 2005, 246-256.
	In article		View Article
[3]	C. Berge, Graphs and Hypergraphs: North Holland Amsterdam, 1973.
	In article
[4]	C. Berge: Theory of graphs & its applications, Methuen, London, 1962.
	In article
[5]	E. J. Cockayne and S. T. Hedetniemi: Disjoint independent dominating sets in graphs, Discrete Math, Vol. 15, 1976, 213-222.
	In article		View Article
[6]	E. J. Cockayne and S. T. Hedetniemi: Towards a theory of domination in graphs, Networks, Vol. 7, 1977, 247-261.
	In article		View Article
[7]	F. S. Roberts: Graph theory and its application to problems of society, SIAM, Philadelphia, 1978, 57-64.
	In article		View Article
[8]	O. Margenstern: The Colaboration between Oskar Margenstern and John Von Neumann on the theory of games, Journal of Economic Literature, Vol. 14, 1976, 805-816.
	In article
[9]	O. Ore: Theory of graphs, Amer. Math. Soc. Trans., Vol. 38 (Amer. Math. Soc., providence, RI, 1962), 206-212.
	In article
[10]	S. B. Lin, C. Lin: Trees and forests with large and small independent indices, Chinese J. math., Vol. 23 (3), 1995, 199-210.
	In article
[11]	T. W. Haynes, S. T. Hedetniemi, P. J. Slater: Domination in graphs: Advanced Topics, Morcel Dekker, New York, 1998.
	In article
[12]	T. W. Haynes, S. T. Hedetniemi, P. J. Slater: Fundamentals of domination in graphs, Morcel Dekker, New York, 1998.
	In article