Embedding edge-colored complete graphs in binary affine spaces

Peter J. Cameron*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


Under what conditions on an edge-coloring of a complete graph can it be embedded in an affine space over GF(2) in such a way that two edges have the same color if and only if they are parallel? Necessary conditions are that each vertex lies on at most one edge of each color, and the "parallelogram property" (if {a, b} ∼ {c, d} then {a, c} ∼ {b, d}); these are not sufficient. In this paper, several sufficient conditions are given, including one depending on the classification of graphs with the "triangle property" by Shult and Seidel. If a coloring is embeddable, its automorphisms are all induced by affine transformations; this is used to study colorings with doubly transitive automorphism groups. Connections with coding theory, elliptic geometry, and difference sets are mentioned.

Original languageEnglish
Pages (from-to)203-215
Number of pages13
JournalJournal of Combinatorial Theory, Series A
Issue number2
Publication statusPublished - 1 Jan 1976


Dive into the research topics of 'Embedding edge-colored complete graphs in binary affine spaces'. Together they form a unique fingerprint.

Cite this