• About
    • Login
    View Item 
    •   Institutional Repository Home
    • Electronic Theses and Dissertations
    • Electronic Theses and Dissertations
    • View Item
    •   Institutional Repository Home
    • Electronic Theses and Dissertations
    • Electronic Theses and Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Browse

    All of Institutional RepositoryCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsDepartmentThis CollectionBy Issue DateAuthorsTitlesSubjectsDepartment

    My Account

    LoginRegister

    Characterizations of Graphs Without Certain Small Minors

    Gaslowitz, Joshua Zachary
    : https://etd.library.vanderbilt.edu/etd-03262018-125736
    http://hdl.handle.net/1803/11465
    : 2018-04-06

    Abstract

    This dissertation contributes new results about minor-restricted families of graphs to the field of structural graph theory. A graph G contains a graph H as a minor if H can be formed from G through a sequence of vertex deletions, edge deletions, and edge contractions. Graph minors are of interest in part because they often serve as obstructions to having important properties. For example, Wagner's Theorem characterizes graphs that can be embedded in the plane as exactly those which contain neither K<sub>5</sub> nor K<sub>3,3</sub> as minors. It is known that the set of graphs embeddable in any fixed surface, and indeed each minor-closed set of graphs, has a similar characterization in terms of a finite list of forbidden minors --- though finding this list is, in general, very difficult. The related problem of fixing a graph H and describing the family of H-minor-free graphs is also difficult, although a very rough structural description that applies to any H is known. A precise characterization of such families has been found for several specific minors, sometimes with an additional constraint on the connectivity of the graphs. Our work provides a characterization and enumeration of 4-connected K<sub>2,5</sub>-minor-free graphs and a characterization of planar 4-connected DW<sub>6</sub>-minor-free graphs, where DW<sub>6</sub> is the join of C<sub>6</sub> with two independent vertices.
    Show full item record

    Files in this item

    Icon
    Name:
    Gaslowitz-Dissertation.pdf
    Size:
    886.7Kb
    Format:
    PDF
    View/Open

    This item appears in the following collection(s):

    • Electronic Theses and Dissertations

    Connect with Vanderbilt Libraries

    Your Vanderbilt

    • Alumni
    • Current Students
    • Faculty & Staff
    • International Students
    • Media
    • Parents & Family
    • Prospective Students
    • Researchers
    • Sports Fans
    • Visitors & Neighbors

    Support the Jean and Alexander Heard Libraries

    Support the Library...Give Now

    Gifts to the Libraries support the learning and research needs of the entire Vanderbilt community. Learn more about giving to the Libraries.

    Become a Friend of the Libraries

    Quick Links

    • Hours
    • About
    • Employment
    • Staff Directory
    • Accessibility Services
    • Contact
    • Vanderbilt Home
    • Privacy Policy