• 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 DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister

    Characterisation and Hamiltonicity of K_{1,1,t}-minor-free Graphs: A Fan-based Approach

    O'Connell, Kelly Mary
    : https://etd.library.vanderbilt.edu/etd-03202018-112132
    http://hdl.handle.net/1803/10964
    : 2018-04-02

    Abstract

    This dissertation presents some new results in certain areas of structural graph theory. In particular we are concerned with graph minors, and classes of graphs characterised in part by forbidding certain minors. There are many important results on classes of minor-free graphs, for example Wagner's Theorem, which states that a graph is planar if and only if it does not contain K_5 or K_{3,3} as a minor. We work specifically with classes of graphs that do not have a complete multipartite graph K_{1,1,t} as a minor. We introduce a type of induced subgraph called a fan and show that several graph properties are preserved under operations with these fans, allowing us to inductively prove significant results for classes of 3-connected K_{1,1,t}-minor-free graphs. Our first result is a complete structural characterisation of 3-connected K_{1,1,4}-minor-free graphs. We also prove counting results for these, and characterise those that are planar and those that are Hamiltonian. Secondly, we prove a Hamiltonicity result for the class of 3-connected planar K_{1,1,5}-minor-free graphs. In particular, we prove that with one exception, every 3-connected planar K_{1,1,5}-minor-free graph is Hamiltonian. The exception is the well-known Herschel graph, a bipartite graph on eleven vertices.
    Show full item record

    Files in this item

    Icon
    Name:
    KellyOconnell.pdf
    Size:
    609.5Kb
    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