Rainbow Disconnection Colorings In Graphs

This paper mainly studies the rainbow disconnection colorings of graphs.Let G be a nontrivial edge-colored connected graph.An edge-cut R of G is called a rainbow edgecut if no two of its edges are colored the same.An edge-colored graph G is rainbow disconnected if for every two vertices u and v of G,there exists a rainbow u-v-edge-cut separating them.For a connected graph G,the rainbow disconnection number of G,denoted by rd(G),is defined as the smallest number of colors that are needed in order to make G rainbow disconnected.We know that there are two ways to study the connectivity of graphs,one is to use paths,and the other is to use cuts.The rainbow connection coloring is to study the colored connectivity of edge-colored graphs by using paths.So it is natural to consider using cuts to study the colored connectivity of edged-colored graphs.In 2018,Chartrand et al.first discussed the colored connectivity of an edge-colored graph from the perspective of rainbow edge-cuts by introducing the concept of rainbow disconnection colorings of graphs.In fact,the rainbow disconnection number has the following application background.In some illegal commodity transactions,we hope to stop the transaction in time and send out a signal(a certain frequency).On the one hand,we need to block all the roads between the two cities and identify the interception locations based on different signals;on the other hand,we want to use as few frequencies as possible in order to reduce costs.Therefore,we want to know what is the minimum frequency required to meet the above requirements? Treat each city as a vertex.If there is a road between two cities,we add an edge between the two vertices,and use G to denote the resulting graph.Give an edge-coloring for G,where the color on the edge corresponds to the frequency of the road.Therefore,the above problem is equivalent to calculating the rainbow disconnection number of the graph G.This thesis is organized as follows.In Chapter 1,we introduce some basic definitions and notations in graph theory.Then we present the background and related concepts of the rainbow disconnection colorings of graphs.Finally,we give an overview of the results of the rainbow disconnection numbers of graphs.In Chapter 2,for a given rainbow disconnection number,we first determine the maximum number of edges of a connected graph by constructing an extreme graph,which solve a conjecture proposed by Chartrand et al.Furthermore,we obtain two kinds of Erd(?)s-Gallai-type problems of the rainbow disconnection numbers of graphs.In addition,we study the Nordhaus-Gaddum-type problem of the rainbow disconnection numbers of graphs,and completely characterize the graphs that reach the upper bound.In Chapter 3,by the properties of the rainbow disconnection numbers of graphs and the results of the rainbow disconnection numbers of some special graphs,we get an equivalent relationship between rd(G)and the famous Four-Color Theorem,and propose a conjecture similar to the Vizing Theorem,that is,the rainbow disconnection number of a graph is either equal to its upper edge-connectivity,or equal to its upper edge-connectivity plus 1.Then we get that for an odd integer k,there are infinitely many k-edge-connected k-regular graphs to reach the upper and lower bounds of the conjecture,respectively,and give some results to further support our conjecture.Finally,we obtain the upper bounds of rd(G)on other parameters.In Chapter 4,in order to obtain a colored version of the Menger Theorem,we introduce the concept of strong rainbow disconnection colorings of graphs and get some basic properties about it.At the same time,we discuss the relationship between the strong rainbow disconnection number and the rainbow disconnection number of a graph.In Chapter 5,we study the complexity of the(strong)rainbow disconnection colorings of graphs.We show that it is NP-complete to decide if rd(G)= 3(or srd(G)= 3)for a connected cubic graph G.Then we prove that for a given edge-colored graph and two vertices of the graph,it is NP-complete to determine whether there is a rainbow(minimum)edge-cut between these two vertices.In Chapter 6,we list some problems that can be further studied.