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 -