Dear Label_Name,

Greetings! I hope you are well.

I am writing on behalf of an international publishing house, Science and Education Publishing, USA (http://www.sciepub.com).

Science and Education Publishing (SciEP) is a multidisciplinary open access publisher of Journals covering the fields of Science, Technology and Medicine. All SciEP publications are subject to high-quality peer review, editorial and production processes and are freely available online.

Welcome to the April, 2013 edition of SciEP newsletter, providing monthly summaries of articles on science & education related topics of interest to scientist and professionals. The mission of our journals is to provide an open access forum for publishing new findings on issues pertinent to scientific and academic field. We also invite you to submit original research papers, review articles, short reports, or case studies are considered for publication in our Multidisciplinary Journals.

American Journal of Public Health Research
DOI: 10.12691/ajphr-1-1-3

The Implementation of a Tele-Homecare System with Service Oriented Architecture and HL7 Message Transmission Standard
Ching-Sung Wang

American Journal of Medical and Biological Research
DOI: 10.12691/ajmbr-1-1-2

The Influence of Ethanol on Pyruvate Kinases Activity in Vivo, in Vitro, in Silico
Lelevich Sergey Vladimirovich, Khrustalev Vladislav Victorovich, Barkovsky Eugene Victorovich, Shedogubova Tatyana Aleksandrovna

American Journal of Medical Sciences and Medicine
DOI: 10.12691/ajmsm-1-1-1

Clinical and Histological Features in Wegener Granulomatosis
Li Cavoli Gioacchino, Passantino Rita, Bono Luisa, Tortorici Calogera, Ferrantelli Angelo, Giammarresi Carlo, Rotolo Ugo

American Journal of Infectious Diseases and Microbiology
DOI: 10.12691/ajidm-1-1-2

The Curse of Lymphatic Filariasis: Would the Continual Use of Diethylcarbamazine Eliminate this Scourge in Papua New Guinea?
Anne Lanham, Lillian Mwanri

We have released issues of some journals on February 2013.
American Journal of Public Health Research
American Journal of Medical Sciences and Medicine
American Journal of Medical and Biological Research
American Journal of Pharmacological Sciences
American Journal of Clinical Medicine Research
American Journal of Nursing Research
American Journal of Cancer Prevention
American Journal of Medicine Studies
American Journal of Infectious Diseases and Microbiology
American Journal of Cardiovascular Disease Research
American Journal of Biomedical Research
American Journal of Mechanical Engineering
American Journal of Microbiological Research
Journal of Preventive Medicine
American Journal of Food and Nutrition
American Journal of Hypertension Research
American Journal of Sports Science and Medicine
Journal of Cancer Research and Treatment
American Journal of Zoological Research
Journal of Biomedical Engineering and Technology
American Journal of Microbiological Research
Biomedical Science and Engineering

We are pleased to announce that submissions are now being accepted for peer review for all the journals across all our subject areas in SciEP.

Please submit your manuscript via our online submission system:
http://www.sciepub.com/author/signin

To unsubscribe from our mailing list, please click on the following link: unsubscribe

I am looking forward to hearing from you.

Kind regards,

David Rain
Email:join@sciepub.com
Science and Education Publishing (http://www.sciepub.com)

Domination Numbers of Graphs Containing Vertex-Disjoint Cycles in Graphs

Omprakash Sikhwal*, Rekha Lahoti

Devanshi Tutorial, Keshw Kunj, Mandsaur (M.P.), India

Abstract: Domination in graphs has been an extensively researched branch of graph theory. In a graph, a domination set is a subset S of the vertices such that every vertices of V-S is adjacent to a vertex of S. The main object of this article is to study the domination numbers of graph containing vertex disjoint cycles with some identities of domination set and independent set. Further, we present some identities related to domination number, upper domination number, Independence number and independent domination number of graphs containing vertex-disjoint cycles.

Keywords: independent numbers, domination numbers, graph

Citation: Omprakash Sikhwal, Rekha Lahoti, Domination Numbers of Graphs Containing Vertex-Disjoint Cycles in Graphs. Turkish Journal of Analysis and Number Theory, 5 (1). 1-4. January 2017. doi:10.12691/tjant-5-1-1

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

[picture] | (4.1)

Suppose for every , , then a vertex such that

[picture] | (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.
[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.
[3]   | C. Berge, Graphs and Hypergraphs: North Holland Amsterdam, 1973.
[4]   | C. Berge: Theory of graphs & its applications, Methuen, London, 1962.
[5]   | E. J. Cockayne and S. T. Hedetniemi: Disjoint independent dominating sets in graphs, Discrete Math, Vol. 15, 1976, 213-222.
[6]   | E. J. Cockayne and S. T. Hedetniemi: Towards a theory of domination in graphs, Networks, Vol. 7, 1977, 247-261.
[7]   | F. S. Roberts: Graph theory and its application to problems of society, SIAM, Philadelphia, 1978, 57-64.
[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.
[9]   | O. Ore: Theory of graphs, Amer. Math. Soc. Trans., Vol. 38 (Amer. Math. Soc., providence, RI, 1962), 206-212.
[10]   | S. B. Lin, C. Lin: Trees and forests with large and small independent indices, Chinese J. math., Vol. 23 (3), 1995, 199-210.
[11]   | T. W. Haynes, S. T. Hedetniemi, P. J. Slater: Domination in graphs: Advanced Topics, Morcel Dekker, New York, 1998.
[12]   | T. W. Haynes, S. T. Hedetniemi, P. J. Slater: Fundamentals of domination in graphs, Morcel Dekker, New York, 1998.