DMGT

Discussiones Mathematicae Graph Theory 24(1) (2004) 109-114
DOI: https://doi.org/10.7151/dmgt.1217

SOME APPLICATIONS OF pq-GROUPS IN GRAPH THEORY

Geoffrey Exoo

Department of Mathematics and Computer Science
Indiana State University
Terre Haute, IN 47809, USA
e-mail: g-exoo@indstate.edu

Abstract

We describe some new applications of nonabelian pq-groups to construction problems in Graph Theory. The constructions include the smallest known trivalent graph of girth 17, the smallest known regular graphs of girth five for several degrees, along with four edge colorings of complete graphs that improve lower bounds on classical Ramsey numbers.

Keywords: Ramsey number, edge coloring, cage, degree, girth, Cayley graph.

2000 Mathematics Subject Classification: 05C25, 05C35, 05C55.

References

[1]	G. Exoo, Some New Ramsey Colorings, Electronic J. Combinatorics 5 (1998) #R29.
[2]	G. Exoo, A Small Trivalent Graph of Girth 14, to appear.
[3]	M. Hall, The Theory of Groups (The Macmillan Company, New York, 1959).
[4]	S.P. Radziszowski, Small Ramsey Numbers, Dynamic Survey DS1, Electronic J. Combinatorics 1 (1994) pp. 28.
[5]	G. Royle, Cubic Cages, ⟨ `http://www.cs.uwa.edu.au/`∼ `gordon/cages/index.html`⟩ , February, 2001 (Accessed: January 20, 2002).
[6]	M. Schönert et al, Groups, Algorithms and Programming, version 4 release 2, Department of Mathematics, University of Western Australia.

Received 4 February 2002
Revised 28 August 2002