A STUDY OF MATCHINGS AND DOMINATIONS IN GRAPH THEORY
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
INTRODUCTION
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
CHAPTER THREE
3.1: Graph Theory 10
3.1.16 Hamiltonian Graph 16
3.2 Graph Isomorphism 18
CHAPTER FOUR
4.0 MATCHING, INDEPENDENCE AND DOMINATION
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
Summary, conclusion and Recommendation
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 wide spread 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.
1.2 Aim of the Study
The aim of this study is to understand and develop a better understanding of the theoretical properties of Matchings and Domination
1.3 Basic concepts
1.3.1 Definition
Graph: A graph is a pair G = (V,E) consisting of a vertex set V(G) together with an edge set E(G) (or E), which is comprised of 2-element subsets of V, the endpoints of an edge.
Two vertices that form an edge are adjacent vertices and so they are neighbors. The order of a graph G denoted n(G) refers to the number of vertices and the size of the graph e(G) is the number of edges. The degree of a vertex v is the number of edges with v as at least one of its endpoints.
When working with a graph we often need to focus on a certain subset of the graph. Such a subset is more formally set out in the following definitions:
A subgraph has vertices and edges belonging to G.
Figure 1.1 A graph
Example 2: Consider the graph Let G = {V, E} where V = {1, 2, 3} and E = {12,13}. Then the drawing below represents this graph:
Figure 1.2
The graph G = ({1,2,3},{12,13})
Example 3. Let V = {p1, p2, p3, p4, p5, p6} be a set of six people at a party, and suppose p1 shook hands with p2 and p4, p3shook hands with p4 and p5 and p6 shook hands. Let G = {V, E} be the graph with edge set E consisting of pairs of people who shook hands.
Then E = {p1p2, p1p4, p3p4, p3p5, p3p6, p5p6}.
A drawing of G is given below:
Figure 1.3
Example 4: Let Z denote the set of integers2 and let V = {(x, y) ϵ Z x Z : 0 ≤x ≤2,0 ≤y ≤2}.
Thus Z={… ,2,1,0,1,2,3,…}. Then Z x Z is the Cartesian product, which is the set of pairs (x,y) such that x ϵ Z and y ϵ Z.
Then V is just the set of points in the plane with integer co-ordinates between 0 and 2. Now suppose G = (V, E) is the graph where E is the set of pairs of vertices of V at distance 1 from each other. In other words, (x,y) and (x',y') are adjacent if and only if (x,x')+(y+y')=1. We check that the edge set is
E={(0,0)(0,1),(0,0)(1,0),(0,1)(0,2),(1,0)(2,0),(1,0)(1,1),(1,1)(1,2),
(1,1)(2,1),(0,1)(1,1),(0,2)(1,2),(2,0)(2,1),(2,1)(2,2),(1,2)(2,2)}.
This is a cumbersome way to write the edge set of G, as compared to the drawing of G below, which is much easier to absorb.
Figure 1.4 The grid graph G
Example 5: let G be the graph with vertex set V = {v1, v2, v3, v4, v5, v6, v7} and edge set E = {v1v4, v1v7, v2v3, v2v6, v2v7, v3v4, v3v5, v3v7, v4v5, v4v6, v5v6, v5v7}
Two drawings of G are shown below
Figure 1.5a Figure 1.5b
A Graph G with vertex set V (G) = {a,b,c,d,e} and edge set E(G) = {u,v,w,x,y,z}. n(G) = 5 and e(G) = 6 with the vertices a, b, and c having the largest degree of 3. a and b are adjacent and are said to be neighbors as they are the endpoints of edge x.
1.3.2 Definition
An induced subgraph G[A] has vertex set A ⊆ V (G) obtained by taking A and all edges of G having both endpoints in A.
Figure 1.6 gives an example of a graph with a subgraph and induced subgraph.
A graph G (b) A subgraph H of G. G[A] with vertex set A = V = {a,b,c,d,e,f,g,h,i}. {a,b,c,d,e,f,h}.(c) An induced subgraph with vertex set
Figure 1.2: A graph G with induced subgraph H and induced subgraph G[A].
1.3.3 Definition
A connected graph G has a u, v-path for each set of distinct vertices u, v. That is every vertex u, has a path to every vertex v, u,v ∈ V (G), u 6= v.
1.3.4 Definition
A bipartite graph G has vertex sets X and Y such that each edge in G has one vertex in X and one vertex in Y.
Observe an example a bipartite graph that is connected in Figure 1.3a and of a disconnected graph in Figure 1.3b the connected graph is comprised of one component while the disconnected graph is composed of three components, one of which is a singleton vertex.
(a) A connected graph that is bipartite. (b) A disconnected graph with 3 components
Figure 1.7: An example of a bipartite graph that is connected and a disconnected graph.
1.4 Scope and limitations
There are a few limitations to the study of matchings and domination problems. First, it is still an open question whether the problem of finding in finding a maximum matching is NP-hard. study of matching problems is often limited by the size of the graphs that can be analyzed, for example it can be difficult to analyze large graphs due to the computational complexity of the algorithms.
Click “DOWNLOAD NOW” below to get the complete Projects
FOR QUICK HELP CHAT WITH US NOW!
+(234) 0814 780 1594
Login To Comment