The Number Of Decomposition With Edges And Cycles Of Some Product Graph And Cube Graph

In 1966,Erdos,Goodman and pósa put forward to a conjecture:Everygraph withn vertices can be covered by cn edges and cycles for some constant c such thateach edge is covered exactly once.It is very difficult to prove the conjecture,even sofar people know nothing about the constant c .The number of a graph decompositionwith edges and cycles was defined ,and the number of decomposition with edges andcycles of some graphs is worked out in Xie Wei Qiang's paper.In his paper, he putforward to this conjecture:whenm andn are big enough,the number of decompositionwith edges and cycles of graph p_m ×p_n is(m -1)(n -1).In Chapter 2,we prove the conjecture above is wrong.We provide the number ofdecomposition with edges and cycles of the product graph p_m ×p_n whenm = 2,3,4,5.We provide the upper bound of the number of decomposition with edgesand cycles when m and n are odd.In the end,we provide the number ofdecomposition with edges and cycles of some product graph.In Chapter 3,through leting vertex ofn -cube be correspond with nonnegativeinteger, we provide the number of decomposition with edges and cycles of somen -cube graphs or upper and lower bound.