PARTITIONING STRONGLY REGULAR GRAPHS (BALANCED INCOMPLETE BLOCK DESIGNS, ASSOCIATION SCHEMES).

Persistent Link:
http://hdl.handle.net/10150/187829
Title:
PARTITIONING STRONGLY REGULAR GRAPHS (BALANCED INCOMPLETE BLOCK DESIGNS, ASSOCIATION SCHEMES).
Author:
GOSSETT, ERIC JAMES.
Issue Date:
1984
Publisher:
The University of Arizona.
Rights:
Copyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.
Abstract:
A strongly regular graph can be design partitioned if the vertices of the graph can be partitioned into two sets V and B such that V is a coclique and every vertex in B is adjacent to the same number of vertices in V. In this case, a balanced incomplete block design can be defined by taking elements of V as objects and elements of B as blocks. Many strongly regular graphs can be design partitioned. The nation of design partitioning is extended to a partitioning by a generalization of block designs called order-free designs. All strongly regular graphs can be partitioned via order-free designs. Order-free designs are used to show the nonexistence of a strongly regular graph with parameters (50,28,18,12). The existence of this graph was previously undecided. A computer algorithm that attempts to construct the adjacency matrix of a strongly regular graph (given a suitable order-free design) is presented. Two appendices related to the algorithm are included. The first lists all parameter sets (n,a,c,d) with n ≤ 50 and a ≠ d that satisfy the standard feasibility conditions for strongly regular graphs. Additional information is included for each set. The second appendix contains adjacency matrices (with the partitioning by cocliques and order-free designs exhibited) for most of the parameter sets in the first appendix. The theoretical development is presented in the context of association schemes. Partitioning by order-free designs extends naturally to any association scheme when cocliques are generalized to {Ø,i} -cliques. This extended partitioning is applied to generalized hexagons.
Type:
text; Dissertation-Reproduction (electronic)
Keywords:
Partitions (Mathematics); Graph theory.
Degree Name:
Ph.D.
Degree Level:
doctoral
Degree Program:
Mathematics; Graduate College
Degree Grantor:
University of Arizona

Full metadata record

DC FieldValue Language
dc.language.isoenen_US
dc.titlePARTITIONING STRONGLY REGULAR GRAPHS (BALANCED INCOMPLETE BLOCK DESIGNS, ASSOCIATION SCHEMES).en_US
dc.creatorGOSSETT, ERIC JAMES.en_US
dc.contributor.authorGOSSETT, ERIC JAMES.en_US
dc.date.issued1984en_US
dc.publisherThe University of Arizona.en_US
dc.rightsCopyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.en_US
dc.description.abstractA strongly regular graph can be design partitioned if the vertices of the graph can be partitioned into two sets V and B such that V is a coclique and every vertex in B is adjacent to the same number of vertices in V. In this case, a balanced incomplete block design can be defined by taking elements of V as objects and elements of B as blocks. Many strongly regular graphs can be design partitioned. The nation of design partitioning is extended to a partitioning by a generalization of block designs called order-free designs. All strongly regular graphs can be partitioned via order-free designs. Order-free designs are used to show the nonexistence of a strongly regular graph with parameters (50,28,18,12). The existence of this graph was previously undecided. A computer algorithm that attempts to construct the adjacency matrix of a strongly regular graph (given a suitable order-free design) is presented. Two appendices related to the algorithm are included. The first lists all parameter sets (n,a,c,d) with n ≤ 50 and a ≠ d that satisfy the standard feasibility conditions for strongly regular graphs. Additional information is included for each set. The second appendix contains adjacency matrices (with the partitioning by cocliques and order-free designs exhibited) for most of the parameter sets in the first appendix. The theoretical development is presented in the context of association schemes. Partitioning by order-free designs extends naturally to any association scheme when cocliques are generalized to {Ø,i} -cliques. This extended partitioning is applied to generalized hexagons.en_US
dc.typetexten_US
dc.typeDissertation-Reproduction (electronic)en_US
dc.subjectPartitions (Mathematics)en_US
dc.subjectGraph theory.en_US
thesis.degree.namePh.D.en_US
thesis.degree.leveldoctoralen_US
thesis.degree.disciplineMathematicsen_US
thesis.degree.disciplineGraduate Collegeen_US
thesis.degree.grantorUniversity of Arizonaen_US
dc.identifier.proquest8504121en_US
dc.identifier.oclc693397997en_US
All Items in UA Campus Repository are protected by copyright, with all rights reserved, unless otherwise indicated.