1 |
Codes, graphs and designs related to iterated line graphs of complete graphsKumwenda, Khumbo January 2011 (has links)
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.
|
2 |
Codes, graphs and designs related to iterated line graphs of complete graphsKumwenda, Khumbo January 2011 (has links)
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.
|
3 |
Codes, graphs and designs related to iterated line graphs of complete graphsKumwenda, Khumbo January 2011 (has links)
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
|
4 |
Codes, graphs and designs related to iterated line graphs of complete graphsKumwenda, Khumbo January 2011 (has links)
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+l(Kn) using certain elementary relations.
Codes from incidence designs of complete graphs, Kn' and neighbourhood designs
of their line graphs, £1(Kn) (the so-called triangular graphs), have been
considered elsewhere by others. We consider codes from incidence designs of
Ll(Kn) and L2(Kn), and neighbourhood designs of L2(Kn) and L3(Kn). In
each case, the basic parameters of the codes are determined.
Further, we introduce a family of vertex-transitive graphs Rn that are
embeddable into the strong product Ll(Kn) ~ K2' of triangular graphs and
K2' a class that 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, Rn 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 Rn and
Hn and determine their parameters.
The discussion is concluded with a look at complements of Rn and Hn,
respectively denoted by Rn and Hn. Among others, the complements rn
are contained in the union of the categorical product Ll(Kn) x Kn' and the
categorical product £1(Kn) x Kn (where £1(Kn) is the complement of the
iii
triangular graph £1(Kn)). As with the other graphs, we have also considered
codes from the span of incidence matrices of Rn and Hn and determined some
of their properties.
In each case, automorphisms of the graphs, designs and codes have been
determined. For the codes from incidence designs of triangular graphs, embeddings
of Ll(Kn) x K2 and complements of complete porcupines, we have
exhibited permutation decoding sets (PD-sets) for correcting up to terrors
where t is the full error-correcting capacity of the codes. For the remaining
codes, we have only been able to determine PD-sets for which it is possible
to correct a fraction of t-errors (partial permutation decoding). For these
codes, we have also determined the number of errors that can be corrected
by permutation decoding in the worst-case.
|
Page generated in 0.1121 seconds