| A graph is supereulerian if it contains a spanning Eulerian subgraph or, equivalently, contains a spanning closed trail. Those properties of supereulerian graphs that can be used to decide efficiently whether or not a given graph is supereulerian are a classical topic of research in graph graph.The main work in this thesis includes:1. Review the background, basic concepts, importance and status of the research of supereulerian graphs. List some related problems.2. By employing a classic method of judging whether a given degree sequence is graphic sequence, followed by an analysis of the property of a collapsible sequence or an Eulerian sequence step by step, sufficient conditions are established for a degree sequence to be the graphic sequence of a supereulerian graph.3.For an integer r≥0, a graph G is r -supereulerian graph if for any X ? E ( G)with X≤r, G has a spanning Eulerian subgraph H such that X ? E ( H). r -Eulerian-connected graph, strongly r -Eulerian-connected graph and r -edge-connected graph could be defined similarly. After analyzing the minimum value of k that guarantees a k -edge-connected graph is r -supereulerian, this thesis summarizes the minimum value of k to ensure a k -edge-connected to belong to one of the three Eulerian-connected graphs mentioned as before.4. The contraction method, introduced by Catlin, of judging whether a graph is supereulerian is a powerful tool for the study of supereulerian graphs. This thesis presents an algorithm for matching even subset of vertexes into pairs to ensure that the path between the vertices in a same pair is distinct and all the paths are edge-disjoint. On this basis, and taking into account the properties of some special kinds of graphs, this thesis presents a theorem for judging whether a graph is supereulerian. Finally, by applying this theorem, it is proved that, when m, n≥4, a m×n grid is supereulerian.
|
PDF Full Text Request