Research On The (Induced) Matching Extensions And Graph Invariants Based On Distance Of Cayley Graphs

The definition of Cayley graphs was introduced by Arthur Cayley in 1878 to explain the concept of abstract groups which are described by a set of generators,thus giving a graph representation of the group.In the last 70 years,the theory of Cayley graphs has been grown into a substantial branch in algebraic graph theory.The study of Cayley graph involves some classical pure mathematical problems,such as the classification and isomorphism of finite groups,but also has many applications in molecular biology and coding theory.Because Cayley graphs have good symmetry and fault tolerance,many interconnection network topologies often use Cayley graph as the prototype.The diameter of Cayley graphs can be used as a measure of the maximum communication delay of these Internet networks,and various connectivity degrees can be used as one of the measures of network fault tolerance.Among them,the study of various properties and graph invariants of Cayley graphs on n-element symmetry group Gn has played a very crucial and important role.A connected graph Γ with a perfect matching of order at least 2k+2 is said to be k-extendable if for every matching M of k edges can be extended to a perfect matching of Γ.The extendability number of Γ is the maximum integer k such thatΓ is k-extendable.Let S be a subset of transpositions and generate n-element symmetry group Sn.In this thesis,we determine the extendability number of connected Cay(Sn,S)and some even order Unitary Cayley graphs characterize a connected IM-extendable Cay(Sn,S),and also study the graph invariants of several types of Cayley graphs related to distance.This thesis is divided into seven chapters,specifically as follows:The first chapter introduces some main concepts and notations in graph theory and algebra to be used in this thesis,and then summarizes the research background and known results of Cayley graphs,and finally introduces the main results of this thesis.The second chapter we study the matching extensions of connected Cayley graphs generated by transpositions.We use the definition of k-extendable to directly get the extendability number of Cayley graphs generated by transpositions tree,and then give the structural properties of the Cayley graphs generated by transpositions,and finally use an equivalent condition of k-extendable given by Plummer obtain that the extendability number of Cay(Sn,S)is |S|-1.The third chapter we study the induced matching extensions of connected Cayley graphs generated by transpositions.First we give two types of 4-cycle and custom structure notions in Cay(Sn,S),and then obtain that Cay(Sn,S)is IMextendable if and only if T(S)has true twins.In addition,we give a linear algorithm for checking true twins in T(S).In chapter 4,we study some distance-based graph invariants of several special classes of Cayley graphs generated by transpositions.We calculate the Hosoya polynomials of TNn,BSn and STn,and the Wiener index and Eccentric distance sum of TNn,BSn.We also used MATLAB to calculate the specific values of these graph invariants when n≤5.In chapter 5,we further study some properties of the star graphs,and obtain the independent perfect dominating sets and domination number of STn.A lower bound on the size of maximum induced matching and an upper bound on the number of strong edge colorings in STn are also given.In Chapter 6,we study the extensibility of some Unitary Cayley graphs of even order,and then use an equivalent condition of k-extendable given by Plummer to obtain the extendability number of Unitary Cayley graphs Xn when n=2r1p2r2 or n=2r1pr2p3r3.The seventh chapter of this thesis makes a summary and puts forward some problems to be solved in the future.