• Login
    JavaScript is disabled for your browser. Some features of this site may not work without it.
    Some applications of matching theorems 
    •   QMRO Home
    • Queen Mary University of London Theses
    • Theses
    • Some applications of matching theorems
    •   QMRO Home
    • Queen Mary University of London Theses
    • Theses
    • Some applications of matching theorems
    ‌
    ‌

    Browse

    All of QMROCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects
    ‌
    ‌

    Administrators only

    Login
    ‌
    ‌

    Statistics

    Most Popular ItemsStatistics by CountryMost Popular Authors

    Some applications of matching theorems

    View/Open
    VAUGHANSomeApplications2010.pdf (463.1Kb)
    Metadata
    Show full item record
    Abstract
    This thesis contains the results of two investigations. The rst concerns the 1- factorizability of regular graphs of high degree. Chetwynd and Hilton proved in 1989 that all regular graphs of order 2n and degree 2n where > 1 2 ( p 7 􀀀 1) 0:82288 are 1-factorizable. We show that all regular graphs of order 2n and degree 2n where is greater than the second largest root of 4x6 􀀀 28x5 􀀀 71x4 + 54x3 + 88x2 􀀀 62x + 3 ( 0:81112) are 1-factorizable. It is hoped that in the future our techniques will yield further improvements to this bound. In addition our study of barriers in graphs of high minimum degree may have independent applications. The second investigation concerns partial latin squares that satisfy Hall's Condition. The problem of completing a partial latin square can be viewed as a listcolouring problem in a natural way. Hall's Condition is a necessary condition for such a problem to have a solution. We show that for certain classes of partial latin square, Hall's Condition is both necessary and su cient, generalizing theorems of Hilton and Johnson, and Bobga and Johnson. It is well-known that the problem of deciding whether a partial latin square is completable is NP-complete. We show that the problem of deciding whether a partial latin square that is promised to satisfy Hall's Condition is completable is NP-hard.
    Authors
    Vaughan, Emil Richard
    URI
    http://qmro.qmul.ac.uk/xmlui/handle/123456789/1286
    Collections
    • Theses [3321]
    Copyright statements
    The copyright of this thesis rests with the author and no quotation from it or information derived from it may be published without the prior written consent of the author
    Twitter iconFollow QMUL on Twitter
    Twitter iconFollow QM Research
    Online on twitter
    Facebook iconLike us on Facebook
    • Site Map
    • Privacy and cookies
    • Disclaimer
    • Accessibility
    • Contacts
    • Intranet
    • Current students

    Modern Slavery Statement

    Queen Mary University of London
    Mile End Road
    London E1 4NS
    Tel: +44 (0)20 7882 5555

    © Queen Mary University of London.