The Structure Properties Of Some Special Graphs

Graph theory,as a branch of discrete mathematics,is widely applied to computer,biology,chemistry and other science subjects,as well as data network,logistics,transportation,management and many other practical application problems.Among many research problems in graph theory,it is an important research in the structural graph theory to decompose a relatively complex graph into some special subgraphs with disjoint edges or disjoint vertices,which is called the problem of edge set decomposition and vertex set cover.Edge coloring is an important content of the coloring problems.Compared with other coloring problems such as vertex coloring,there are many conjectures on edge coloring problem to be solved urgently,such as the independence number conjecture of edge chromatic critical graph proposed by Vizing.In this paper,we study the vertex set cover and packing problem of some special graphs,the independence number problem and the 2-factor problem of edge chromatic critical graphs as follows:If the vertex set of a graph contains a spanning subgraph which consists of a sequence of vertex disjoint cycles and K₂,then the spanning subgraph is called a weak cycle partition of the graph(WCP for short),where K₂ denotes a complete graph consisting of two vertices.If a weak cycle partition of a graph consists ofk elements,it is called ak-weak cycle partition of the graph(k-WCP for short).Hu and Li proved that if a graph G of order n at least k+12 with a k-WCP and the degree sum of any two non-adjacent vertices is at least (2n+k-4)/3,then G contains a k-WCP with at most one subgraph isomorphic to K₂.In this paper,inspired by the above results,we study the existence of the above special k-WCP under the Fan-type condition,and proved that if a graph G of order n at least k+12 with a k-WCP and the maximal degree of any two non-adjacent vertices is at least (2n+k-4)/6,then G contains a k-WCP with at most one subgraph isomorphic to K₂.The result is a generalization of the previous results obtained by Professors Hu and Li.A simple graph G is called?-critical if its edge chromatic number is?+1 and chromatic index number of each proper subgraph of G is less than the chromatic index number of G,where?denotes the maximum degree of G.For?-critical graphs,Vizing proposed two famous conjectures,the 2-factor conjecture and the independence number conjecture,which are:each?-critical graph contains a 2-factor;And the independence number of the?-critical graph is at most half of its order.In this paper,by the Meredith extension of a?-critical graph,we obtain the function relationship of the independence number between any?-critical graphs and a specific class of ?-critical graph with the minimum degree of ?-1;Furthermore,we can transform the problem of studying the independence number of ?-critical graphs into a specific kind of ?-critical graph with the minimum degree of ?-1.In this paper,we also give the upper bound of the independence numbers of this special kind of ?-critical graph with the minimum degree of ?-1.Furthermore,in this paper,we give a conclusion that a?-critical graph contains a 2-factor if and only if any Meredith extension graph constructed from any its vertex contains a 2-factor by the properties of bipartite graphs and the structure of Meredith extension.