Semester

Summer

Date of Graduation

2009

Document Type

Dissertation

Degree Type

PhD

College

Eberly College of Arts and Sciences

Department

Mathematics

Abstract

The research of my dissertation was motivated by the conjecture of Thomassen that every 4-connected line graph is hamiltonian and by the conjecture of Matthews and Sumner that every 4-connected claw-free graph is hamiltonian. Towards the hamiltonian line graph problem, we proved that every 3-connected claw-free Z8-free graph is hamiltonian, where Z8 is obtained by identifying one end-vertex of P9 with one vertex of a triangle; let hc( G) denote the least integer m such that the iterated line graph Lm(G) is Hamilton-connected, we showed that k -- 1 ≤ hc( G) ≤ max{lcub}diam(G), k -- 1{rcub}, where k is the length of a longest path whose internal vertices, if any, have degree 2 in G, and also showed that kappa3(G) ≤ hc(G) ≤ kappa3(G) + 2 where kappa3(G) is the least integer m such that Lm(G) is 3-connected; moreover, hc(G) ≤ | V(G)| -- Delta(G) + 1.;Chvatal and Erdos showed that the graph G with connectivity kappa(G) not less than its independence number alpha(G) (i.e. kappa(G) ≥ alpha( G)) is hamiltonian. In this dissertation, we characterized the 2-connected graph G with kappa(G) ≥ alpha( G) -- 1.;On the other side, we studied the number of components of a 2-factor in a graph to approach its hamiltonicity. In this dissertation, we gave a bound for the number of components of a 2-factor in the line graph of G if max{lcub}d(x), d( y){rcub} ≥ n-mp -- 1 holds for any xy ∉ E(G) and |U| ≠ 2, where U = {lcub}v : d(v) < n-mp -- 1{rcub}, p is a positive integer and mu a nonnegative integer.;As an application of graph theory in electrical engineering, we studied the inverse problems on networks at the end of the dissertation and showed that the conductivities in a tree network can be uniquely determined by measurements at the boundary of the voltages generated by imposed currents.

Download

Share

COinS