Return to search

Excluding a Weakly 4-connected Minor

A 3-connected graph $G$ is called weakly 4-connected if min $(|E(G_1)|, |E(G_2)|) \leq 4$ holds for all 3-separations $(G_1,G_2)$ of $G$. A 3-connected graph $G$ is called quasi 4-connected if min $(|V(G_1)|, |V(G_2)|) \leq 4$. We first discuss how to decompose a 3-connected graph into quasi 4-connected components. We will establish a chain theorem which will allow us to easily generate the set of all quasi 4-connected graphs. Finally, we will apply these results to characterizing all graphs which do not contain the Pyramid as a minor, where the Pyramid is the weakly 4-connected graph obtained by performing a $\Delta Y$ transformation to the octahedron. This result can be used to show an interesting characterization of quasi 4-connected, outer-projective graphs.

Identiferoai:union.ndltd.org:LSU/oai:etd.lsu.edu:etd-04042016-220803
Date22 April 2016
CreatorsD'souza, Kimberly Sevin
ContributorsDing, Guoli, Oxley, James, Oporowski, Bogdan, Litherland, Richard, Delzell, Charles, Terrell, Milton
PublisherLSU
Source SetsLouisiana State University
LanguageEnglish
Detected LanguageEnglish
Typetext
Formatapplication/pdf
Sourcehttp://etd.lsu.edu/docs/available/etd-04042016-220803/
Rightsunrestricted, I hereby certify that, if appropriate, I have obtained and attached herein a written permission statement from the owner(s) of each third party copyrighted matter to be included in my thesis, dissertation, or project report, allowing distribution as specified below. I certify that the version I submitted is the same as that approved by my advisory committee. I hereby grant to LSU or its agents the non-exclusive license to archive and make accessible, under the conditions specified below and in appropriate University policies, my thesis, dissertation, or project report in whole or in part in all forms of media, now or hereafter known. I retain all other ownership rights to the copyright of the thesis, dissertation or project report. I also retain the right to use in future works (such as articles or books) all or part of this thesis, dissertation, or project report.

Page generated in 0.0025 seconds