The Determination Of Supereulerian Graphs And Research Of Catlin-Conjecture

The supereulerian graph problem is an important study in the circle of graph theory, which mainly includes two aspects: one is the determination of supereulerian graphs and the other is the edge-problem. The dissertation investigated the problems mentioned above under the contraction method. In the paper, there is a new conception - sub-collapsible subgraph - presented, around which there are some discussions made. The main results of the paper are following: Theorem 7 G is a simple graph. Then G ∈ SL There are edge-disjoint pathsp1,p2,…Ps whose endpoints are different in pair such that O(G)={endpoints of pi| i= 1,2, …s }and G -UsE(pi) is connected.Proposition 3.2 If m, n are natural numbers, no less than 2, then mxn -grid graphs are supereulerian when m, n are not 3 simultaneously.Theorem 8 Suppose H is a subgraph of a connected graph G. If H is a sub-collapsible subgraph of G, thenG/H∈ SL G∈SL.Theorem 9 Assume G=(V,E) is supereulerian, |V(G)|=n, δ(G) denotes the minimal degreeof G. If δ(G) ≥ max{4,n-4/5} , then there is a spanning eulerian subgraph H such thatTheorem 10 Assume G=(V,E) is supereulerian and k3 - free , |V(G)|=n, δ(G) denotes the minimal degree of G. If 6(G) ≥n/10, then there exists a spanning eulerian subgraph H, such that|E(H )| ≥ 2/3|E(G)| , or there are trivial branches in G-E(H).Proposition 6.1 H is a simple graph. If there is an even set X of V(H) such that every subgraph H X of H whose odd-vertex set is X is not spanning one, then there is a supergraph G of H, such that G/H∈ SL G∈SL fails.