Cheng Zhao

Date of Graduation

1993

Document Type

Thesis

Abstract

There are five chapters in this thesis. In Chapter I, we present some frequently used definitions and notations, and describe the main results in this thesis. In Chapter II, edge-colouring and total colouring of graphs are discussed. The core {dollar}G\\sb{lcub}\\Delta{rcub}{dollar} is the subgraph of G induced by the vertices of maximum degree. If {dollar}G\\sb{lcub}\\Delta{rcub}{dollar} is a forest then Fournier (24) showed that G is Class 1. Therefore if G is Class 2, {dollar}G\\sb{lcub}\\Delta{rcub}{dollar} must contain cycles. A natural question is this: what is the chromatic index of G if {dollar}G\\Delta{dollar} is a union of vertex disjoint cycles? Further information about this question is given in this Chapter. Also we survey several important known results on the total colouring of graphs and prove some new results about total colouring. In Chapter III, we consider the cycle cover problem. The main result in this Chapter is that if G is a 2-connected simple graph of order n (n {dollar}\\ge{dollar} 7) and w is a smallest (1, 2)-eulerian weight of graph G, then {dollar}\\vert E\\sb{lcub}w=even{rcub}\\vert{dollar} {dollar}\\le{dollar} n {dollar}-{dollar} 4, except for a specified family of graphs. A consequence is that, if G admits a nowhere-zero 4-flow and is of order at least 7, except for a specified family of graphs, the total length of a shortest cycle covering is at most {dollar}\\vert V(G)\\vert{dollar} + {dollar}\\vert E(G)\\vert{dollar} {dollar}-{dollar} 4. This result generalizes some previous results. In Chapter IV, we consider the edge-reconstruction of planar graphs. We prove that, if G is a 3-connected planar graph and contains no vertex of degree 4, then G is edge reconstructible. This generalizes a result of J. Lauri. In Chapter V, we study a particular case of the problem of determining for which values of k there is a k-to-1 continuous map from a graph G onto a graph H. We concentrate on the case when H is a cycle, and k = 3, and we characterize all possible connected graphs G.

Download

Share

COinS