Study For Monochromatic Connections Of Graphs

The study of the structure of edge-colored graphs is one of the leading topics in graph theory research.As one of the problems,the connectivity of edge-colored graphs has developed rapidly.The monochromatic connectivity of graphs is an emerging issue that has gradually become active in recent years.Caro and Yuster introduced the concept of monochromatic connection of graphs in 2011.A connected graph G is monochromatically connected if there is a monochromatic path joining each two vertices of G.An edge-coloring of a connected graph G is a monochromatic connection coloring?MC-coloring,for short?if the coloring makes graph G monochromatically connected.For a connected graph G,the monochromatic connection number mc?G?of G is defined to be the maximum number of colors allowed in an MC-coloring of G It is clear that mc?G??|E?G?|-|V?G?|+2 for any connected graph GIn recent decades,researchers have given some upper bound and constraints of lower bound.Among them,Caro and Yuster prove that connected graphs without triangles and with diameters not less than 3 reach this lower bound.Jin et al.found more graph classes to reach this lower bound and also gave some upper bound.In this master thesis,we study some restrictions to reach the lower bound of monochromatic connectivity problem,and found some graph classes to meet the lower bound.The followings are main contentsIn the first chapter,the basic concepts and terminology are introduced.The research background and current status of the monochromatically connected theory are also elaborated in detail,and finally the main results are described brieflyIn the second chapter,we further sublimates the conclusion that Jin et al.have reached the lower bound,proves that the monochromatic connection numbers of the graphs without hourglass union triangles and the graphs without K4-? ? meet the lower bound,and proves that the monochromatic connection numbers of the connected minimal graphs with diameter of 2 reach the lower boundIn the third chapter,we mainly studies under what conditions the graph contain-ing K4 can satisfy the lower bound.We prove that the monochromatic connection numbers of the graph can satisfy the lower bound when any two subgraphs isomorphic to K4 are vertex disjoint or edge disjoint in graph GIn the fourth chapter,we mainly studies under what conditions the graph contain-ing K₁+P₄ can satisfy the lower bound.We prove that the monochromatic connection numbers of the graph can satisfy the lower bound when any two subgraphs isomorphic to K₁+P₄ are vertex disjoint in graph GIn the last chapter,we mainly consider under what conditions the graph containing fish graph can satisfy the lower bound.We prove that the monochromatic connection numbers of the graph can satisfy the lower bound when any two subgraphs isomorphic to fish graph are vertex disjoint in graph G.