Total Rainbow Connectivity And Proper Connectivity Of Several Special Graphs

Graph coloring is one of the most significant topic in graph theory,and lots of open problems,for example the four color problem,are active problems studied by many researchers at home and abroad.Connectivity of a graph is one of the most important properties in graph theory,rainbow connectivity and proper connectivity are strengthening of the classical connectivity and important graph coloring problems.The rainbow connection number of a graph which is applied to measure the safety of a network was introduced and studied by Chartrand et al.[9]in 2008.Rainbow connection numbers of graphs and it's related problems have received considerable attention,and become a hot topic in graph theory.This thesis includes six chapters,we mainly investigate the total rainbow connectivity and proper connectivity of several special graphs.In Chapter 1,we introduce the definition and give the basic notation and terminology used in this thesis.In Chapter 2,we show that if G is a bridgeless outerplanar graph with order n and diameter 2,then 3 ?trc(G)?5.Morever,if n?11,then trc(G)=5.Then we improve the main result of[19],we determine the bridgeless outerplanar graph of order n and diameter 2 with rainbow connection numbers 2 and 3.Finally,we revise the main result of[40],and prove that if n ?4,then rc(Cn*)=?i=1nli.We also show that if n?3,then rvc(Kn*)=rvc(Cn*)=n and trc(Kn*)=trc(Cn*)=n+?i=1nli.In Chapter 3,we first study the rainbow vertex connection numbers and the total rainbow connection numbers of Middle graphs.We show the rainbow vertex connection numbers and the total rainbow connection numbers of M(Ps),M(Cs),M(K1,s),M)Ks).Next,we study the rainbow vertex connection numbers and the total rainbow connection numbers of Total graphs.We determine the the rainbow vertex connection numbers and the total rainbow connection numbers of T(Ps),T(Cs),T(K1,s),T(Ks).In Chapter 4,we first show some results on pc(D)and spc(D).Then we show the(strong)proper connection numbers of cacti digraphs.We prove that if Q is an(n,q)-cactus with q?2,pc(Q)=spc(Q)=2 when ni is even and 1?i?q,and pc(Q)=spc(Q)=3 in others.Finally,we study the proper connection numbers of circulant digraphs.We also show that if 2?k?n-2,then 2?spc(Cn([k]))?3.In Chapter 5,we first research some basic results on pvc(D)and spvc(D).In addition,a tight upper bound is provided for the proper vertex connection number of strong digraphs by a method different from[14].Then,we research the values of(strong)proper vertex connection numbers of cacti and circulant digraphs,and we show the tight examples of strong proper vertex connection of circulant digraphs.Moreover,we prove that if T is a strongly connected tournament with n? 4,then pvc(T)=1 for diam(T)=2,and pvc(T)=2 for diam(T)?3.In Chapter 6,as a generalization,we introduce the concept of total proper connection of strong digraphs,and show that the upper bound of total proper connection number of strong digraphs is 4,and the upper bound is tight.Moreover,results on the(strong)total proper connection numbers of biorientations of graphs,circle digraphs,circulant digraphs and cacti digraphs are presented.