Balanced colourings of strongly regular graphs

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

A colouring of a strongly regular graph is an allocation of colours (or treatments) to the vertices of the graph. Such a colouring is balanced if every pair of distinct colours occurs equally often on the ends of an edge. When the graph is the complete regular multipartite graph a balanced colouring is just a balanced incomplete-block design, or 2-design.

Some constructions are given. For example, colourings of the triangular graph give balanced designs for experiments where the experimental units are unordered pairs of people. An analogue of Fisher's inequality is proved.

In this context, strongly regular graphs may be generalized to arbitrary association schemes. When the association scheme is a collection of circular blocks then a colouring is balanced if the design in blocks is a 2-design and there is undirectional neighbour balance at all distances around the circle.
Original languageEnglish
Pages (from-to)73-90
Number of pages18
JournalDiscrete Mathematics
Volume293
Publication statusPublished - 2005

Keywords

  • association scheme
  • balanced design
  • strongly regular graph

Fingerprint

Dive into the research topics of 'Balanced colourings of strongly regular graphs'. Together they form a unique fingerprint.

Cite this