Book contents
- Frontmatter
- Contents
- Introduction
- 1 A brief introduction to design theory
- 2 Strongly regular graphs
- 3 Quasi-symmetric designs
- 4 Strongly regular graphs with no triangles
- 5 Polarities of designs
- 6 Extension of graphs
- 7 Codes
- 8 Cyclic codes
- 9 Threshold decoding
- 10 Reed-Muller codes
- 11 Self-orthogonal codes and designs
- 12 Quadratic residue codes
- 13 Symmetry codes over GF(3)
- 14 Nearly perfect binary codes and uniformly packed codes
- 15 Association schemes
- References
- Index
6 - Extension of graphs
Published online by Cambridge University Press: 05 April 2013
- Frontmatter
- Contents
- Introduction
- 1 A brief introduction to design theory
- 2 Strongly regular graphs
- 3 Quasi-symmetric designs
- 4 Strongly regular graphs with no triangles
- 5 Polarities of designs
- 6 Extension of graphs
- 7 Codes
- 8 Cyclic codes
- 9 Threshold decoding
- 10 Reed-Muller codes
- 11 Self-orthogonal codes and designs
- 12 Quadratic residue codes
- 13 Symmetry codes over GF(3)
- 14 Nearly perfect binary codes and uniformly packed codes
- 15 Association schemes
- References
- Index
Summary
In this section we shall be considering graphs from a slightly different point of view, as incidence structures in their own right (as remarked in Chapter 2). In particular, a regular graph is a 1-design with k = 2, and conversely (provided we forbid repeated blocks). An interesting question is: when do such 1-designs have extensions? Since 2-designs with k = 3 are so common, this problem is too general, and we shall usually impose extra conditions on the extension. Extensions of designs were originally used by Witt, Hughes and Dembowski for studying transitive extensions of permutation groups, and it might be expected that extensions of regular graphs would be useful in the study of doubly transitive groups. This is indeed the case.
If we are extending a design by adding an extra point p, we know all the blocks of the extension containing p - these are obtained simply by adjoining p to all the old blocks - but it is in the blocks not containing p that possible ambiguities arise. Let us then suppose, as a first possibility, that we have a set Δ of triples, called blocks, in which the blocks not containing a point p are uniquely determined in a natural way by those containing p; in particular let us suppose that, when we know which of {pqr}, {pqs} and {prs} are blocks, we can decide whether {qrs} is a block.
- Type
- Chapter
- Information
- Graph Theory, Coding Theory and Block Designs , pp. 38 - 43Publisher: Cambridge University PressPrint publication year: 1975