Skip navigation
  • Home
  • Browse
    • Communities
      & Collections
    • Browse Items by:
    • Publication Date
    • Author
    • Title
    • Subject
    • Department
  • Sign on to:
    • My MacSphere
    • Receive email
      updates
    • Edit Profile


McMaster University Home Page
  1. MacSphere
  2. Open Access Dissertations and Theses Community
  3. Open Access Dissertations and Theses
Please use this identifier to cite or link to this item: http://hdl.handle.net/11375/8743
Title: Decompositions of complete multipartite graphs and group divisible designs into isomorphic factors
Authors: Fronček, Dalibor
Advisor: Rosa, Alexander
Department: Mathematics
Keywords: Mathematics;Mathematics
Publication Date: Apr-1994
Abstract: <p>A multipartite graph Km₁, m₂, ..., mr (group divisible design GDD) is (t,d)-decomposable if it can be decomposed into t factors with the same diameter d. The graph Km₁, m₂, ..., mr (design GDD) is (t,d)-isodecomposable if the factors are moreover isomorphic. Km₁, m₂, ..., mr (GDD) is admissible for a given t if its number of edges (or blocks) is divisible by t. fr(t,d) or gr(t,d), respectively, is the minimum number of vertices of a (t,d)-decomposable or (t,d)-isodecomposable complete r-partite graph, respectively. gr(t,d) is the minimum number such that for every p ≥ gr(t,d) there exists a (t,d)-isodecomposable r-partite graph with p vertices, and hr(t,d) is the minimum number such that all admissible r-partite graphs with p ≥ hr (t,d) vertices are (t,d)-isodecomposable.</p> <p>We completely determine the spectrum of all bipartite and tripartite (2,d)-isodecomposable graphs. We show that f₂(2,d) = g₂(2,d) = g₂(2,d) =h₂(2,d) and f₃(2,d) = g₃(2,d) = g₃(2,d) for each d, that is possible, while h₃(2,2) = ∞ (i.e., for any given p, there is an admissible graph with more than p vertices which is not (2,2)-isodecomposable), h₃(2,3) = g₃(2,3) +2, h₃(2,4) = g₃(2,4) and h₃(2,5) = g₃(2,5) + 1.</p> <p>For complete four-partite graphs we completely determine the spectrum of (2, d)-isodecomposable graphs with at most one odd part. For the remaining admissible graphs, namely for those with all odd parts, we show that there is no such (2,5)-isodecomposable graph. For d = 2,3,4 we solve the problem in this class completely for the graphs Kn,n,n,m and Kn,n,m,m.</p> <p>For all r ≥ 5 we determine smallest (2,d)-isodecomposable r-partite graphs for all possible diameters and show that also in these cases always gr(2,d) = gr'(2,d). Some values of hr(2,d) are also determined.</p> <p>We furthermore prove that if a GDD with r ≥ 3 groups is (2,d)-isodecomposable, then d ≤ 4 or d = ∞. We show that for every admissible n there exists a (2,3)- and (2,4)-isodecomposable 3 - GDD(n,3), i.e., a GDD with 3 groups of cardinality n and block size 3.</p> <p>Finally, we determine the spectrum of the designs 3 - GDD(n,3) which are decomposable into unicyclic factors.</p>
URI: http://hdl.handle.net/11375/8743
Identifier: opendissertations/3922
4939
1794691
Appears in Collections:Open Access Dissertations and Theses

Files in This Item:
File SizeFormat 
fulltext.pdf
Open Access
2.6 MBAdobe PDFView/Open
Show full item record Statistics


Items in MacSphere are protected by copyright, with all rights reserved, unless otherwise indicated.

Sherman Centre for Digital Scholarship     McMaster University Libraries
©2022 McMaster University, 1280 Main Street West, Hamilton, Ontario L8S 4L8 | 905-525-9140 | Contact Us | Terms of Use & Privacy Policy | Feedback

Report Accessibility Issue