MATCHINGS AND DOMINATIONS IN GRAPH THEORY
| Format: Ms Word | 1-5 Chapters | Table of Content|
INSTANT PROJECT MATERIAL DOWNLOAD
Study Level: BTech, BSc, BEng, BA, HND, ND or NCE
Amount: ₦4,000.00
ABSTRACT
Matching independence and domination are fundamental concepts in graph theory that play pivotal roles in understanding the structural and algorithmic aspects of graphs. Matching independence explores the notion of constructing sets of non-overlapping edges, while domination focuses on identifying subsets of vertices that efficiently cover an entire graph. This abstract provides an overview of these two concepts, highlighting their definitions, properties, and applications in various fields. Matching independence entails the search for maximum sets of edges in a graph, where no two edges share a common vertex. It finds application in problems related to network design, scheduling, and combinatorial optimization. Dominating sets, on the other hand, aim to identify subsets of vertices in a graph such that every vertex is either in the dominating set or adjacent to a vertex within it.
Domination concepts find practical utility in areas such as surveillance systems, sensor networks, and resource allocation. This abstract emphasizes the significance of matching independence and domination as fundamental building blocks in graph theory, offering valuable insights into the structure and behavior of graphs. Researchers and practitioners in mathematics, computer science, and related fields continue to explore these concepts to unravel their complexities and leverage them for solving a diverse range of real-world problems.
TABLE OF CONTENTS
DECLARATION.. i
CERTIFICATION.. iii
DEDICATION.. iv
ACKNOWLEDGMENT. v
TABLE OF CONTENTS. vii
CHAPTER ONE. 1
INTRODUCTION.. 1
1.1 Background to the study. 1
1.2 Aim of the Study. 2
1.3 Basic concepts. 2
1.4 Scope and limitations. 6
CHAPTER TWO.. 7
CHAPTER THREE. 10
3.1: Graph Theory. 10
3.1.16 Hamiltonian Graph. 16
3.2 Graph Isomorphism.. 18
CHAPTER FOUR. 19
4.0……………………………………………………. MATCHING, INDEPENDENCE AND DOMINATION.. 19
4.3 ……………………………………………………………………………………. Independence and Covers. 23
4.4 Domination. 25
4.4.5…………………………………………………………………………….. Independent Dominating set. 27
Definition 4.4.6. 28
Definition 4.4.7. 28
Theorem 4.4.8. 29
CHAPTER FIVE. 31
Summary, conclusion and Recommendation. 31
5.1 Summary. 31
5.2 Conclusion. 31
5.3 Recommendation. 32
REFERENCES. 33
CHAPTER ONE
INTRODUCTION
1.1 Background to the study
The study of graph can be traced back to the time of Leonhard Euler who devised in 1735 a problem known as the “seven Bridges of Konigsberg”. In this problem someone has to cross all the bridges only once and in a continuous sequence. A problem that Euler prove to have no solution by representing it as a set of nodes and links (vertices and edges). This led the foundation of graph and its subsequent improvements.
In general, graph theory is the study of graphs which are mathematical structures used to model pairwise relations between objects from a certain collection. Graphs are among the most ubiquitous models of both natural and human-made structures. Its study has had widespread ramifications due to applications in many other fields of study like Physics, Chemistry, Computer Science (algorithm and computation), Social Science, Linguistics, Biology, Biochemistry, Cryptography, Engineering, Operations Research (scheduling) etc.
At first, the usefulness of Euler’s ideas and of “graph theory” itself was found only in solving puzzles and in analyzing games and other recreations. In the mid 1800s, however, people began to realize that graphs could be used to model many things that were of interest in society. For instance, the “Four Color Map Conjecture,” introduced by DeMorgan in 1852, was a famous problem that was seemingly unrelated to graph theory. The conjecture stated that four is the maximum number of colors required to color any map where bordering regions are colored differently. This conjecture can easily be phrased in terms of graph theory, and many researchers used this approach during the dozen decades that the problem remained unsolved.
The field of graph theory began to blossom in the twentieth century as more and more modeling possibilities were recognized and the growth continues. It is interesting to note that as specific applications have increased in number and in scope, the theory itself has developed beautifully as well.
Of the numerous problems concerning sets of edges or set of vertices in graphs, many of this deal with the idea of independence (in which every two elements in the set are not adjacent). Such a set of edges is a matching in a graph. The fact that two adjacent vertices u and v result in the edge uv gives rise to two other fundamental concepts in graph theory, namely covers and domination.
An area of graph theory that has received increased attention during recent decades is that of dominations in graphs.
USE THIS MATERIALS AS A GUIDE FOR YOUR PERSONAL RESEARCH WORK (IF PROPERLY CITED)
PAY ₦3,000 HERE TO DOWNLOAD MATERIALS
Account Number: 0709546102
Access Bank: Savings
Account Name: Emmanuel Idorenyin Samuel.