Semester

Summer

Date of Graduation

2009

Document Type

Dissertation

Degree Type

PhD

College

Eberly College of Arts and Sciences

Department

Mathematics

Committee Chair

Hong-Jian Lai.

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