TY - JOUR

T1 - Embedding edge-colored complete graphs in binary affine spaces

AU - Cameron, Peter J.

PY - 1976/1/1

Y1 - 1976/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=49549133855&partnerID=8YFLogxK

U2 - 10.1016/0097-3165(76)90064-9

DO - 10.1016/0097-3165(76)90064-9

M3 - Article

AN - SCOPUS:49549133855

SN - 0097-3165

VL - 21

SP - 203

EP - 215

JO - Journal of Combinatorial Theory, Series A

JF - Journal of Combinatorial Theory, Series A

IS - 2

ER -