Return to search

Codes, graphs and designs related to iterated line graphs of complete graphs

Philosophiae Doctor - PhD / In this thesis, we describe linear codes over prime fields obtained from incidence designs of iterated line graphs of complete graphs Li(Kn) where i = 1, 2. In the binary case, results are extended to codes from neighbourhood designs of the line graphs Li+1(Kn) using certain elementary relations. Codes from incidence designs of complete graphs, Kn, and neighbourhood designs of their line graphs, L1(Kn) (the so-called triangular graphs), have been considered elsewhere by others. We consider codes from incidence designs of L1(Kn) and L2(Kn), and neighbourhood designs of L2(Kn) and L3(Kn). In each case, basic parameters of the codes are determined. Further, we introduce a family of vertex-transitive graphs Γn that are embeddable into the strong product L1(Kn)⊠  K2, of triangular graphs and K2, a class which at first sight may seem unnatural but, on closer look, is a repository of graphs rich with combinatorial structures. For instance, unlike most regular graphs considered here and elsewhere that only come with incidence and neighbourhood designs, Γn also has what we have termed as 6-cycle designs. These are designs in which the point set contains vertices of the graph and every block contains vertices of a 6-cycle in the graph. Also, binary codes from incidence matrices of these graphs have other minimum words in addition to incidence vectors of the blocks. In addition, these graphs have induced subgraphs isomorphic to the family Hn of complete porcupines (see Definition 4.11). We describe codes from incidence matrices of Γn and Hn and determine their parameters. / South Africa

Identiferoai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:uwc/oai:etd.uwc.ac.za:11394/1760
Date January 2011
CreatorsKumwenda, Khumbo
ContributorsMwambene, Eric, Fish, Washiela, Dept. of Mathematics, Faculty of Science
PublisherUniversity of the Western Cape
Source SetsSouth African National ETD Portal
LanguageEnglish
Detected LanguageEnglish
TypeThesis
RightsUniversity of the Western Cape

Page generated in 0.0026 seconds