TY - JOUR

T1 - Two-graphs and trees

AU - Cameron, Peter J.

PY - 1994/3/15

Y1 - 1994/3/15

N2 - Tsaranov has associated to each two-graph a group generated by elements of order 3. He and Seidel define a map from trees to two-graphs; the Tsaranov group of a two-graph in the image of this map is the even subgroup of the Coxeter group of the tree. In this paper, I will give a simplified account of the map, and also settle a question raised by Seidel and Tsaranov, by characterising the two-graphs in the image of the map (and also a related class of graphs) by forbidden substructures. I also describe a different map from trees to two-graphs, characterise its image by excluded substructures, and use this to give an alternative proof of the first characterisation. Connections with Tsaranov and Coxeter groups, and with countable homogeneous structures, are briefly described.

AB - Tsaranov has associated to each two-graph a group generated by elements of order 3. He and Seidel define a map from trees to two-graphs; the Tsaranov group of a two-graph in the image of this map is the even subgroup of the Coxeter group of the tree. In this paper, I will give a simplified account of the map, and also settle a question raised by Seidel and Tsaranov, by characterising the two-graphs in the image of the map (and also a related class of graphs) by forbidden substructures. I also describe a different map from trees to two-graphs, characterise its image by excluded substructures, and use this to give an alternative proof of the first characterisation. Connections with Tsaranov and Coxeter groups, and with countable homogeneous structures, are briefly described.

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

U2 - 10.1016/0012-365X(92)00468-7

DO - 10.1016/0012-365X(92)00468-7

M3 - Article

AN - SCOPUS:38149148018

SN - 0012-365X

VL - 127

SP - 63

EP - 74

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-3

ER -