The Rainbow(Vertex-)Connected Numbers Of Mycielskian Graphs Of Some Special Graphs

The famous Konigsberg Bridge Problem is the origin of graph theory problem,then graph theory has become an important branch of applied mathematics research.The dyeing of special graphs has always been a hot issue in the field of graph theory,which not only has theoretical value,but also has important practical significance.Connectivity is one of the most important properties in graph theory,there are many ways to strengthen connectivity,such as Hamiltonian,k-connectivity,in addition,rainbow connectivity can also be regarded as a general connectivity enhancement.In 2008,chartrand^[1]and others first introduced and studied the rainbow connectivity of graphs,and determined the number of rainbow connection of some special graphs.Simi-lar to the concept of rainbow connectivity,Krivelevich and Y uster^[2]give the definition of rainbow vertex connectivity.Chakraborty^[3]et al proved that calculating the rainbow con-nected number of a general graph is a N P-difficult problem.Then ChenLin^[4]et al proved that calculating the rainbow vertex connected number of a general graph is a N P-difficult problem.So it is very meaningful to determine the number of rainbow connections for some special graphs.The full text is divided into four chapters:in the first chapter,first introduce some background and development status of rainbow?vertex-?connected graph,then give some basic concepts,terms and symbols used in this paper,and finally enumerate the main results of this paper.In the second chapter,the exact numerical value of the rainbow vertex connected of the Mycielskian graph is given separately.In the third chapter,the exact number of rainbow connected numbers for the Myciel-skian graph is given separately.In the fourth chapter,the exact number of rainbow connected numbers of complement graphs of mycielskian graphs of some special graph is given separately.