Claw-free graphs and line graphs | Posted on:2006-01-14 | Degree:Ph.D | Type:Dissertation | University:West Virginia University | Candidate:Shao, Yehong | Full Text:PDF | GTID:1450390008468361 | Subject:Mathematics | Abstract/Summary: | | The research of my dissertation is motivated by the conjecture of Thomassen that every 4-connected line graph is hamiltonian and by the conjecture of Tutte that every 4-edge-connected graph has a no-where-zero 3-flow. Towards the hamiltonian line graph problem, we proved that every 3-connected N2-locally connected claw-free graph is hamiltonian, which was conjectured by Ryjacek in 1990; that every 4-connected line graph of an almost claw free graph is hamiltonian connected, and that every triangularly connected claw-free graph G with |E( G)| ≥ 3 is vertex pancyclic. Towards the second conjecture, we proved that every line graph of a 4-edge-connected graph is Z 3-connected. | Keywords/Search Tags: | Line graph, Proved that every, Claw-free graph, Conjecture, Hamiltonian | | Related items |
| |
|