Generating the nine-point graphs

Authors:
H. H. Baker, A. K. Dewdney and A. L. Szilard

Journal:
Math. Comp. **28** (1974), 833-838

MSC:
Primary 68A05

MathSciNet review:
0371134

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A program has been written which recently generated all the (unlabelled) nine-point graphs. Written in MACRO-10 assembly language and run on a 165K PDP-10, it generates the complete set of 274,668 graphs in less than six hours. The algorithm on which this program is based is discussed with an emphasis on coding of graphs and various programming techniques designed to save space and time during execution. The methods developed may have applications in other combinatorial generating problems.

**[1]**John E. Blackburn, Henry H. Crapo, and Denis A. Higgs,*A catalogue of combinatorial geometries*, Math. Comp.**27**(1973), 155–166; addendum, ibid. 27 (1973), no. 121, loose microfiche suppl. A12–G12. MR**0419270**, 10.1090/S0025-5718-1973-0419270-0**[2]**D. G. Corneil and C. C. Gotlieb,*An efficient algorithm for graph isomorphism*, J. Assoc. Comput. Mach.**17**(1970), 51–64. MR**0278977****[3]**Frank Harary,*Graph theory*, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London, 1969. MR**0256911****[4]**Selmer M. Johnson,*Generation of permutations by adjacent transposition*, Math. Comp.**17**(1963), 282–285. MR**0159764**, 10.1090/S0025-5718-1963-0159764-2**[5]**R. Morris, "Scatter storage techniques,"*Comm. ACM*, v. 11, 1968, pp. 38-44.**[6]**Ronald C. Read (ed.),*Graph theory and computing*, Academic Press, New York-London, 1972. MR**0329941****[7]**Mark B. Wells,*Elements of combinatorial computing*, Pergamon Press, Oxford-New York-Toronto, Ont., 1971. MR**0277082**

Retrieve articles in *Mathematics of Computation*
with MSC:
68A05

Retrieve articles in all journals with MSC: 68A05

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1974-0371134-8

Keywords:
Graph,
generative enumeration,
graph isomorphism,
filter,
preliminary code,
filtered code,
maximal code

Article copyright:
© Copyright 1974
American Mathematical Society