Semester

Spring

Date of Graduation

2008

Document Type

Dissertation

Degree Type

PhD

College

Eberly College of Arts and Sciences

Department

Mathematics

Committee Chair

Hong-Jian Lai.

Abstract

A circuit is a connected 2-regular graph. A cycle is a graph such that the degree of each vertex is even. A graph G is Hamiltonian if it has a spanning circuit, and Hamiltonian-connected if for every pair of distinct vertices u, v ∈ V( G), G has a spanning (u, v)-path. A graph G is s-Hamiltonian if for any S ⊆ V (G) of order at most s, G -- S has a Hamiltonian-circuit, and s-Hamiltonian connected if for any S ⊆ V( G) of order at most s, G -- S is Hamiltonian-connected. In this dissertation, we investigated sufficient conditions for Hamiltonian and Hamiltonian related properties in a graph or in a line graph. In particular, we obtained sufficient conditions in terms of connectivity only for a line graph to be Hamiltonian, and sufficient conditions in terms of degree for a graph to be s-Hamiltonian and s-Hamiltonian connected.;A cycle C of G is a spanning eulerian subgraph of G if C is connected and spanning. A graph G is supereulerian if G contains a spanning eulerian subgraph. If G has vertices v1, v2, &cdots; ,vn, the sequence (d( v1),d(v2), &cdots; ,d(vn)) is called a degree sequence of G. A sequence d = ( d1,d2, &cdots; ,dn) is graphic if there is a simple graph G with degree sequence d. Furthermore, G is called a realization of d. A sequence d ∈ G is line-hamiltonian if d has a realization G such that L(G) is hamiltonian. In this dissertation, we obtained sufficient conditions for a graphic degree sequence to have a supereulerian realization or to be line hamiltonian.;In 1960, Erdos and Posa characterized the graphs G which do not have two edge-disjoint circuits. In this dissertation, we successfully extended the results to regular matroids and characterized the regular matroids which do not have two disjoint circuits.

Download

Share

COinS