On a Decomposition of Complete Graphs

It is shown, among other results, that for any prime power q, the complete graph on 1+q+q ²+q ³ vertices can be decomposed into a union of 1+q Siamese Strongly Regular Graphs S R G(1+q+q ²+q ³,q+q ²,q–1,q+1) sharing 1+q ² cliques of size 1+q. Acknowledgments.The authors are indebted to a referee for a very extensive report and for many suggestions which improved the presentation of the paper tremendously.AMS Subject Numbers: 05B05, 05B20, 05E30This work was completed while the first author was on sabbatical leave visiting Institute for studies in theoretical Physics and Mathematics, (IPM), in Tehran, Iran. Support and hospitality is appreciated. Supported by an NSERC operating grant.