Some Results On Collapsible Graphs And Dominating Cycles

Content: In this thesis, some results on collapsible graphs and dominating cycles have been worked. In Chapter One, a sufficient condition of 3-edge-connected graphs being collapsible has been discussed by discussing a 4-matching in 3-edge-connected graphs. Let G be a 3-edge-connected simple graph of order n. For a 4-matching M4 of G, let ∑ (M4) denote the sum of the degrees of the eight vertices incident with M4. We show that if ∑ (M4) ≥ 2n+3 for all 4-matchings M4 of G, then either G is collapsible, or G is the Petersen graph. In Chapter Two, we obtain a sufficient condition of a dominating cycle contained in a graph, suppose G is a connected graph with its circumference being g≥6, D1(G) is a set of all one degree vertices in graph G and G-D1(G) is 2-connected .If (?) e, f∈E(G), d(e, f)=3 , naturally d(e)+ d(f) ≥ n-g+2, then G will contain a dominating cycle.