Perfect matching dominating cycles in graphs - A study and applications

Abstract

One of the amazing features of Graph theory is its recognition in all fields of science and engineering. Graph theory is a fertile area of mathematical research. Domination is one of the most important concepts attracting researchers. There are many variations of domination in the literature such as independent domination, total domination, connected domination, paired domination just to name a few. In this series, a vertex-dominating cycle is defined as a cycle in which every vertex of the graph is adjacent to at least one vertex on the cycle. Dominating cycles find immense applications in networks. The objective of this thesis is to introduce a new kind of dominating cycle called perfect matching dominating cycle, characterize, study the nature of these cycles and analyze some parameters associated with it in undirected, simple, connected graphs with a perfect matching. Some of the exciting new applications that are directly associated with perfect matching dominating cycles have also been explored. Perfect matching sequences, perfect matching dominating cycles and perfect matching minor for simple connected graphs G are defined. A perfect matching M in a graph G of even order, say 2n, is a set of mutually non-adjacent edges, which covers all vertices of G. A non repeated finite alternating sequence of edges of G from M and E - M such that each edge is adjacent with the edge preceding and following it, starting and ending at the same edge of M is called perfect matching sequence (PM-sequence). The subgraph with the edges of such a PM sequence of length 2n, denoted as GM, contains a cycle called the perfect matching dominating cycle (pmdc). The graph obtained by contracting all the edges of M is called a PM minor, denoted as GM . The existence of such pmdc is characterized using Hamilton cycles. The necessary and sufficient condition for the existence of a pmdc is that the PM- minor is Hamiltonian. Apart from finding such cycles in general graphs, enumeration ofpmdcs is also carried out for some classes of graphs. It is always convenient to represent graphs using matrices for further processing. Hence the matrix of perfect matching and the reduced matrix of the perfect matching are defined. Some graph parameters related to pmdc are also discussed. Spanning trees play a very important role in any network since it is a basic structure of the network with minimal number of edges but ensuring connectivity. Spanning trees associated with pmdcs are also defined. One very desirable feature expected out of a graph in the study of combinatorial design theory is edge decomposition with certain structural property. This is taken into account and a new kind of decomposition, called n-sun decomposition is offered.The cycle in the n-sun is a pmdc and hence an n-sun decomposition can be regarded as a type of pmdc decomposition. The study of pmdc in graph products like cartesian, strong and tensor products is done. Since strong product is the union of cartesian and tensor, cartesian and tensor products are given more attention. It is interesting to observe that not all product graphs have pmdc for a given choice of perfect matching. Some classes of product graphs which are non Hamiltonian are identified to have pmdc. Two applications of perfect matching dominating cycles and its allied spanning trees are discussed. The first application finds the number of spanning trees containing a given Keknle structure in fullerene molecules. The second application is on Bluetooth devices, in which a procedure is given to find spanning tree structure with maximum simultaneous active piconets in the scattemet. This thesis concludes that PM-sequences and pmdc spanning trees will play a vital role in network. Also pmdc spanning trees will help in message passing from a vertex to all other vertices, with a maximum congestion of 3 links at a node and hence better than using conventional spanning trees where we cannot always expect the congestion to be less. Also there is a lot of scope for future work based on the concepts introduced and analyzed in this thesis.