Title page for ETD etd-06272011-141751

Type of Document Dissertation
Author Warshauer, Lisa
URN etd-06272011-141751
Title Some Classes of Graphs That Are Nearly Cycle-free
Degree Doctor of Philosophy (Ph.D.)
Department Mathematics
Advisory Committee
Advisor Name Title
Oxley, James G. Committee Chair
Ding, Guoli Committee Member
Oporowski, Bogdan S. Committee Member
Perlis, Robert V. Committee Member
Slawson, Vester Carlos Committee Member
Stoltzfus, Neal W. Committee Member
  • graphs
  • cycles
  • minors
  • excluded minor
  • minor-closed
  • series-parallel
  • almost series-parallel
Date of Defense 2011-06-22
Availability unrestricted

A graph is almost series-parallel if there is some edge that one can add to the graph and then contract out to leave a series-parallel graph, that is, a graph with no K4-minor. In this dissertation, we find the full list of excluded minors for the class of graphs that are almost series-parallel. We also obtain the corresponding result for the class of graphs such that uncontracting an edge and then deleting the uncontracted edge produces a series-parallel graph.

A notable feature of a 3-connected almost series-parallel graph is that it has two vertices whose removal leaves a tree. This motivates consideration of those graphs for which there are two vertices whose removal is cycle-free. We find the full list of excluded minors for the class of graphs that have a set of at most two vertices whose removal is cycle-free.

  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  warshauerdiss.pdf 497.80 Kb 00:02:18 00:01:11 00:01:02 00:00:31 00:00:02

Browse All Available ETDs by ( Author | Department )

If you have questions or technical problems, please Contact LSU-ETD Support.