Research Commons
      • Browse 
        • Communities & Collections
        • Titles
        • Authors
        • By Issue Date
        • Subjects
        • Types
        • Series
      • Help 
        • About
        • FAQs
        • Collection Policy
        • OA Mandate Guidelines
        • Guidelines FAQ
        • Contact Us
      • My Account 
        • Sign In
        • Register
      View Item 
      •   Research Commons
      • University of Waikato Theses
      • Masters Degree Theses
      • View Item
      •   Research Commons
      • University of Waikato Theses
      • Masters Degree Theses
      • View Item
      JavaScript is disabled for your browser. Some features of this site may not work without it.

      Star Decompositions of Bipartite Graphs

      Lim, Jin Sean
      Thumbnail
      Files
      thesis.pdf
      1.095Mb
      cyclicSolverOutput.pdf
      531.9Kb
      Citation
      Export citation
      Lim, J. S. (2015). Star Decompositions of Bipartite Graphs (Thesis, Master of Science (MSc)). University of Waikato, Hamilton, New Zealand. Retrieved from https://hdl.handle.net/10289/9303
      Permanent Research Commons link: https://hdl.handle.net/10289/9303
      Abstract
      In Chapter 1, we will introduce the definitions and the notations used throughout this thesis. We will also survey some prior research pertaining to graph decompositions, with special emphasis on star-decompositions and decompositions of bipartite graphs. Here we will also introduce some basic algorithms and lemmas that are used in this thesis.

      In Chapter 2, we will focus primarily on decomposition of complete bipartite graphs. We will also cover the necessary and sufficient conditions for the decomposition of complete bipartite graphs minus a 1-factor, also known as crown graphs and show that all complete bipartite graphs and crown graphs have a decomposition into stars when certain necessary conditions for the decomposition are met. This is an extension of the results given in "On claw-decomposition of complete graphs and complete bigraphs" by Yamamoto, et. al. We will propose a construction for the decomposition of the graphs.

      In Chapter 3, we focus on the decomposition of complete equipartite tripartite graphs. This result is similar to the results of "On Claw-decomposition of complete multipartite graphs" by Ushio and Yamamoto. Our proof is again by construction and we propose how it might extend to equipartite multipartite graphs. We will also discuss the 3-star decomposition of complete tripartite graphs.

      In Chapter 4 , we will discuss the star decomposition of 4-regular bipartite graphs, with particular emphasis on the decomposition of 4-regular bipartite graphs into 3-stars. We will propose methods to extend our strategies to model the problem as an optimization problem. We will also look into the probabilistic method discussed in "Tree decomposition of Graphs" by Yuster and how we might modify the results of this paper to star decompositions of bipartite graphs.

      In Chapter 5, we summarize the findings in this thesis, and discuss the future work and research in star decompositions of bipartite and multipartite graphs.
      Date
      2015
      Type
      Thesis
      Degree Name
      Master of Science (MSc)
      Supervisors
      Cavenagh, Nicholas J.
      Publisher
      University of Waikato
      Rights
      All items in Research Commons are provided for private study and research purposes and are protected by copyright with all rights reserved unless otherwise indicated.
      Collections
      • Masters Degree Theses [1740]
      Show full item record  

      Usage

      Downloads, last 12 months
      80
       
       

      Usage Statistics

      For this itemFor all of Research Commons

      The University of Waikato - Te Whare Wānanga o WaikatoFeedback and RequestsCopyright and Legal Statement