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 Keywords
- excluded minor
- almost series-parallel
Date of Defense 2011-06-22 Availability unrestricted Abstract
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
If you have questions or technical problems, please Contact LSU-ETD Support.