Excluding a Weakly 4-connected Minor

A 3-connected graph $G$ is called weakly 4-connected if min (|E(G₁)|, |E(G₂)|) \leq 4 holds for all 3-separations (G₁,G₂) of $G$. A 3-connected graph $G$ is called quasi 4-connected if min (|V(G₁)|, |V(G₂)|) \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.

Name thesis:degree_name

Doctor of Philosophy (PhD)

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Applied Mathematics

Grantor

Mathematics

Year dc:date.available

2016

Author dc:creator

• D'souza, Kimberly Sevin

• graph theory
• graph minors
• graph decomposition
• Pyramid graph

Statement dc:rights

• unrestricted
• Release the entire work immediately for access worldwide.

Identifier

etd-04042016-220803
https://repository.lsu.edu/gradschool_dissertations/1368

OAI identifier oai:identifier

oai:repository.lsu.edu:gradschool_dissertations-2367