Royle Graphs

The Royle graphs are the two unique simple graphs on eight nodes whose sigma polynomials have nonreal roots (Read and Wilson 1998, p. 265). The sigma polynomials of these graphs are given by

			(1)
			(2)

respectively, each of which has two nonreal roots (and where the members of each pairs are complex conjugates of each other).

The Royle graphs are implemented in the Wolfram Language as GraphData["RoyleGraph1"] and GraphData["RoyleGraph2"].

The numbers of simple graphs having this property on , 2, ... vertices are 0, 0, 0, 0, 0, 0, 0, 2, 42, ..., with the 42 such graphs on 9 vertices illustrated above.

REFERENCES

Read, R. C. and Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, pp. 265 and 287, 1998.